My problem is mainly from this lecture notes on convex optimization here page4

Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer programming problem

\begin{equation*} \begin{aligned} & \underset{}{\text{minimine}} & & \sum_{u,v\in E}|x_u-x_v| \\ & \text{subject to} & & x_s =1 ,x_t=0 &x_v\in \left\{ 0,1\right\} \forall v \in V \end{aligned} \end{equation*}

then we can relax to:

\begin{aligned} & \underset{}{\text{minimine}} & & \sum_{u,v\in E}|x_u-x_v| \\ & \text{subject to} & & x_s -x_t =1 \end{aligned}

for $0 \leq l \leq 1$ we define $S_l:= \left\{v|x_v \geq l\right\} $ then we have $$\sum_{u,v\in E}|x_u-x_v| \geq\int^{1}_{0}|\delta_l(S_l)|dl$$ where $\delta_l(S_l) $ denotes the crossing edge in $S_l$

how to see this inequality ?


1 Answer 1


It's important to first understand how $\delta(S_l)$ changes. When $l = 0$, $S_l$ contains all vertices, and when $l = 1$, $S_l$ contains no vertices. In either case, there is no edge going between $S_l$ and $\overline{S_l}$, so $\delta(S_l) = 0$.

For values of $l$ between $0$ and $1$, $\delta(S_l)$ contains exactly the edges with one endpoint in $S_l$ and one endpoint in $\overline{S_l}$. In particular, if we define

$$f_{ij}(l) =\left\{ \begin{array}{ll} 1 & \mbox{if } l \mbox{ is between } x_i \mbox{ and } x_j \\ 0 & \mbox{otherwise.} \end{array} \right.$$

then we have $$|\delta(S_l)| = \sum_{(i, j) \in \delta(S_l)} 1 = \sum_{\substack{(i,j) \in E \\ i \in S_l \\ j \not\in S_l}} 1 = \sum_{(i, j) \in E} f_{ij}(l).$$

Now let's consider one particular edge, from $u$ to $v$. Because $f_{uv}(\cdot)$ is just $0$ everywhere except for on one interval where it takes on the value $1$, the value of $\int_0^1 f_{uv}(l)\,\mathrm{d}l$ is just the length of the interval on which $f_{uv}(l) = 1$, that is, $|x_u - x_v|$. So

$$\sum_{(u, v) \in E} |x_u - x_v| = \sum_{(u, v) \in E} \int_0^1 f_{uv}(l)\,\mathrm{d}l = \int_0^1 \sum_{(u, v) \in E} f_{uv}(l)\,\mathrm{d}l = \int_0^1 |\delta(S_l)|\,\mathrm{d}l.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.