Skip to main content
added 15 characters in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

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,j)$$i\to j$ is chosen ($1$) or direction $(j,i)$$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_{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}\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}

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,j)$ is chosen ($1$) or direction $(j,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_{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}

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}

Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

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,j)$ is chosen ($1$) or direction $(j,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_{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}