Find the dual of the given min-max LP

Question

I'm trying to find the dual of an LP in graph theory but get stuck.

For a graph $G=((S\cup T), E)$, where $\delta(s)$ denotes the set of edges incident to vertex $s$,

\begin{aligned} \min \max_{s\in S} \sum_{t \in \delta(s)}x(st) & \\ \text { s.t. } \sum_{s \in \delta(t)}x(st) &=1 & \forall t \in T \\ x & \geq 0, \end{aligned} Thanks in advance!

Answer 1

The first step is to deal with the min-max objective function. If you deal with these often enough, you might derive a general rule, but one way to turn this into a standard linear program is as follows.

1. Introduce a new variable $z$, with the intent that in an optimal solution, $$z = \max_{s \in S} \sum_{t \in \delta(s)} x(st).$$
2. To enforce this intent, add the inequalities $$z - \sum_{t \in \delta(s)} x(st) \ge0 \qquad \forall s \in S.$$
3. Now, the objective function will be to minimize $z$. Although the inequalities from step 2 only guarantee that $$z \ge \max_{s \in S} \sum_{t \in \delta(s)} x(st)$$ in a feasible solution, since we are minimizing $z$, it will actually be equal to this maximum in an optimal solution.

Once you have done this, you can start dealing with the LP in the usual way. Since we have a constraint for every $s \in S$, the dual will have a variable for every $s \in S$, as well as a variable for every $t \in T$ coming from the constraints you already had.