Minimizing the degree of outgoing edges in a digraph, does this problem have a name?

Question

I have a problem which can be rephrased in this way.

Suppose $G = (V,E)$ is a digraph (directed graph) and for each $v \in V$ we denote with $\delta^+(v)$ the number of outgoing edges of the vertex $v$.

I'm looking for a way to swap the edges (so $(i,j) \in E$ would become $(j,i)$) so that $\max_{v,w \in V} |\delta^+(v) - \delta^+(w)|$ is minimized.

Does this problem have a name in literature?

Answer 1

The similar problem of finding an orientation to minimize the maximum outdegree is discussed here. You can solve your range minimization problem via integer linear programming as follows. For each undirected edge $(i,j)$, let binary decision variable $x_{i,j}$ indicate whether direction $i\to j$ is chosen ($1$) or direction $j\to i$ is chosen ($0$). Let decision variables $M$ and $m$ represent the maximum and minimum outdegrees, respectively. The problem is to minimize $M-m$ subject to \begin{align} \delta^+(i)&=\sum_{\substack{j\in V:\\(i,j)\in E \lor (j,i)\in E}} x_{i,j} &&\text{for $i\in V$}\\ M &\ge \delta^+(i) &&\text{for $i\in V$}\\ m &\le \delta^+(i) &&\text{for $i\in V$} \end{align}