Tags: optimization, LP
Problem1
Given a undirected weighted graph \(G=(V,E)\), a weight function \(w:E\to \Z_+\) and an integer \(k\), find a \(k\)-edge-connected spanning subgraph of
\(G\) with the minimum weight.
Consider the following LP relaxation,
\[\begin{align*}
\min& \quad \sum_{e\in E} w(e)x_e\\
s.t.& \quad \sum_{e\in \delta(S)}x_e\geq k &&\forall
S\subset V\\
& \quad 0\le x_e \le 1 &&\forall e\in E
\end{align*}\]
Note that \(x_e\le 1\) is necessary
since each edge can only be chosen once. In the paper the authors
mentioned that this kind of constraints are called box constraints and
they usually make LPs difficult to solve (for example, positive covering
LPs can be solved through MWU). There is also a box-free version of LP
relaxation,
\[
\begin{align*}
\min& \quad \sum_{e\in E} w(e)x_e\\
s.t.& \quad \sum_{e\in C\setminus S}x_e\geq
k-|S| &&\forall \text{ cut } C\\
& &&\forall S\in \set{F: |F|\le k-1 \wedge F\subset
C}\\
& \quad \phantom{\sum_{e\in C\setminus S}} x_e\ge
0 &&\forall e\in E
\end{align*}
\] which is box-free but includes exponentially many extra
constraints. I will call the first LP boxLP and the second one
boxlessLP. Any feasible solution to the boxLP is also feasible in the
boxlessLP. For any \(x_e>1\) in a
feasible solution of boxlessLP, we consider those cuts containing \(e\). For such a cut \(C\), \(\sum_{f\in
C\setminus e} x_f\geq k-1\) and thus \(\sum_{e\in C} x_e>1\). Since this holds
for any cut \(C\) containing \(e\), we can certainly decrease \(x_e\) for a smaller objective. Hence, in
the optimal solution to boxlessLP, every \(x_e\) is less than or equal to 1.
In fact, one can see from the proof that enumerating all singletons
\(F=\set{f}\) is sufficient.
References
[1]
P.
Chalermsook, C.-C. Huang, D. Nanongkai, T. Saranurak, P. Sukprasert, S.
Yingchareonthawornchai, Approximating
k-Edge-Connected Spanning
Subgraphs via a Near-Linear
Time LP Solver, in: 49th
International Colloquium on
Automata, Languages, and
Programming (ICALP 2022), Schloss
Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022: pp.
37:1–37:20 10.4230/LIPIcs.ICALP.2022.37.