Problem
Degree splitting
Undirected degree splitting colors the edges of a graph $G = (V, E)$ red and blue so that every node has about as many red as blue edges; directed degree splitting orients the edges so that every node has about as many outgoing as incoming edges. The discrepancy at a node is the difference between the two numbers, and the problem is parametrized by the largest discrepancy allowed.
Runtimes are given in rounds, in terms of the number of nodes $n$ and the maximum degree $\Delta$; $\varepsilon$ is a fixed constant. A discrepancy of $\varepsilon \deg(v) + \mathcal{O}(1)$ at every node is compared as $\varepsilon\Delta$.