---
# System prepended metadata

title: Lecture 8 - Some Primal-Dual Relaxation Problem
tags: [Algorithm]

---

# Lecture 8 - Some Primal-Dual Relaxation Problem

###### tags: `Algorithm`

## Linear Programming (LP) Duality

| Primal      | Dual        |
| ----------- | ----------- |
| $\min c^Tx$ | $\max b^Ty$ |
|  s.t. $$Ax\geq b\\x\geq 0$$           |  s.t. $$A^Ty\leq c\\y\geq 0$$           |
+ For every feasible $x$ and $y$, $c^Tx\geq b^Ty$
+ Thus, $Opt(primal)\geq Opt(dual)$
+ The dual of the dual is the primal
### Meaning of Duality
| $\min$       | $c_1x_1+c_2x_2+...+c_nx_n$                                                          |
| ----------- | ----------------------------------------------------------------------------------- |
| $y_1\geq 0$ | $a_{11}x_1+ a_{12}x_2+...+a_{1n}x_n\geq b_1$                                        |
| $...$       | $...$                                                                               |
| $y_m\geq 0$ | $a_{m1}x_1+ a_{m2}x_2+...+a_{mn}x_n\geq b_m$                                        |
|             | $(\sum_{i=1}^m{y_ia_{i1}})x_1+...+(\sum_{i=1}^m{y_ia_{in}})x_n\geq\sum_{i=1}^m{y_ib_i}$ |
+ If $\sum_{i=1}^ma_{ij}y_i\leq c_j$for all $j$, then $c_1x_1+...+c_nx_n\geq b_1y_1+...+b_my_m$ 
+ That is, we gives a lower bound on the objective function so we want to maximize $b_1y_1+...+b_my_m$
### LP Duality Theorem: $Opt(primal)$ is finite $\iff$ $Opt(dual)$ is finite, and if $x^*$ and $y^*$ are optimal then $c^Tx^*=b^Ty^*$
### Complementary Slackness Conditions 
+ If $x$ and $y$ are optimal
+ Primal conditions: $\forall j$, either $x_j=0$ or $\sum_{i=1}^ma_{ij}y_i=c_j$
+ Dual conditions: $\forall i$, either $y_i=0$ or $\sum_{j=1}^na_{ij}x_j=b_i$
#### Proof
| $\min$       | $c_1x_1+c_2x_2+...+c_nx_n$                                                          |
| ----------- | ----------------------------------------------------------------------------------- |
| $y_1\geq 0$ | $a_{11}x_1+ a_{12}x_2+...+a_{1n}x_n= b_1$                                        |
| $...$       | $...$                                                                               |
| $y_m= 0$ | $a_{m1}x_1+ a_{m2}x_2+...+a_{mn}x_n\geq b_m$                                        |
|             | $(\sum_{i=1}^m{y_ia_i1})x_1+...+(\sum_{i=1}^m{y_ia_in})x_n\geq\sum_{i=1}^m{y_ib_i}$ |
+ If $c_1x_1+...+c_nx_n=b_1y_1+...+b_my_m$, $\forall i$, either $y_i=0$ or $\sum_{j=1}^na_{ij}x_j=b_i$
## Set Cover
### Problem Definition
+ Given
    + Universe $U$ of $n$ elements
    + $S=\{S_1, S_2,..., S_k\}$ is a collection of subsets of $U$
    + Cost function $c:S\to \mathbb Q^+$
+ Goal: Find min cost subcollection of $S$ covering all of $U$
![](https://i.imgur.com/9JJJVlP.png)
+ The **frequency** of an element is the number of sets it is in
+ $f$ is frequency of most frequent element 
+ **NP-hard problem** 
+ **Vertex Cover is Set Cover with $f=2$**
    + Elements: edges 
    + Sets: vertices
    + Each edge associated with $2$ vertices
#### Set Cover as Integer Programming (IP)
+ Indicator variable $x_i\in \{0,1\}$ for each set $S_i$ in $S$
+ The constraint is that we choose at least one of the sets containing each element

| $\min\sum_{i=1}^k{c(S_i)x_i}$ | 
| -------- |
| s.t. $$\sum_{i:e\in S_i}x_i\geq 1, e\in U\\x_i\in \{0,1\}, i=1,2,...,k$$     | 

#### LP relaxation of IP 
+ The constraint is that we choose at least one of the sets containing each element

| $\min\sum_{i=1}^k{c(S_i)x_i}$ | 
| -------- |
| s.t. $$\sum_{i:e\in S_i}x_i\geq 1, e\in U\\x_i\geq 0,i=1,2,...,k$$|

### Method 1 - Rounding 
+ Solve the LP to get OPT solution $x^*$
+ Include $S_j$ in the integer **solution $I$** if $x_j^*\geq\frac{1}{f}$
#### Theorem: The solution $I$ is indeed a set cover
+ For every $e$, by $\sum_{i|e\in S_i}x_i\geq1$ and $|\{i|e\in S_i\}|\leq f$
+ There exists $S_i$ for every $e$ such that $e\in S_i$ and $x_i\geq\frac{1}{f}$
+ So $S_i$ is in solution $I$
#### Theorem(*Hochbaum’ 82*): Rounding is an $f$-approximate algorithm
+ $\sum_{j\in I}c(S_j)\leq\sum_{j\in I}c(S_j)x_j^*f\leq\sum_jc(S_j)x_j^*f=f\sum_jc(S_j)x_j^*\leq f\times OPT$
### Method 2 - Primal-Dual
| Primal                       | Dual                                    |
| ---------------------------- | --------------------------------------- |
|$\min\sum_{i=1}^k{c(S_i)x_i}$ | $\max\sum_{e\in U}y_e$ |
|s.t. $$\sum_{i:e\in S_i}x_i\geq 1,e\in U\\x_i\geq 0,i=1,2,...,k$$ |s.t. $$\sum_{e:e\in S_j}y_e\leq c_j, j=1,2,...,k\\y_e\geq 0, e\in U$$|
+ min-LP is a **covering** and the max-LP is a **packing**
+ Recall: optimal solutions to linear LPs satisfy complementary slackness conditions
+ Iterative method
    +  Begin with initial solutions to primal and dual
    +  Iteratively start satisfying complementary slackness conditions
        +  Modify the primal integrally
    +  Once all conditions are met, the solutions must be optimal
+  What if optimal solution is not integral?
    +  Relax the conditions
+ Complementary Slackness
    + $x_i=0$ or $\sum_{e\in S_i}y_e=c(S_i)$
    + So $S_i$ is included in $I\Rightarrow x_i=1\Rightarrow\sum_{e\in S_i}y_e=c(S_i)$
#### Basic Algorithm
:::info
+ $y\leftarrow 0$
+ $I\leftarrow\emptyset$
+ **while** there exists $e\notin \cup_{S_j\in I}S_j$ **do**
    + Increase the dual variable $y_e$ until $\sum_{e\in S_k}y_e=c(S_k)$ for some $k$
    + $I\leftarrow I\cup\{S_k\}$
+ return $I$ 
:::
![](https://i.imgur.com/B0BQFHb.png)
+ At the beginning the primal conditions are not satisfied, the dual conditions are all satisfied
+ We want some dual conditions to be tight, then the corresponding set is put into $I$
#### Analysis
+ Finally the primal and dual relaxed conditions are all satisfied
+ The final $I$ we get are all tight: $\sum_{e\in S_k}y_e=c(S_k)$ for all $S_k\in I$
    + Because after include $S_k$ in $I$, the $y_e$ in it will not change any more
+ The algorithm is an $f$-approximation algorithm
    + $\sum_{S_j\in I}c(S_j)=\sum_{S_j\in I}\sum_{e\in S_j}y_e=\sum_{e\in U}y_e|\{S_j\in I|e\in S_j\}|\leq f\sum_{e\in U}y_e\leq f\times OPT$
#### LP Relaxation
+ For a minimization LP problem
![](https://i.imgur.com/2dBc51N.png)
+ So $\sum_{e\in U}y_e\leq OPT$
+ In this example, we didn’t get a better approximation than simply rounding the LP
+ But this algorithm is fully combinatorial, and easy to analyze complexity
    + No need to use really solve the LP
## Network Design
### Problem Definition
+ Input
    + Undirected graph $G=(V,E)$
    + Cost function: $c:E\to\Bbb R^+$
    + Connectivity requirements
+ Output
    + Minimum cost subgraph satisfying connectivity requirements
+ Example
    + MST: minimum cost subgraph connecting all vertices
### Steiner Tree
+ Input
    + Set of terminals $T=\{t_1,..., t_k\}\subseteq V$
    ![](https://i.imgur.com/McmruDy.png)
+ Output
    + Minimum cost subgraph connecting $T$
    + **NP-complete**
    ![](https://i.imgur.com/ed5VEOx.png)
#### Algorithm
+ Define complete graph $H$ on $T$
    + $c_G(t_i,t_j)$ is the shortest path in $G$ from $t_i$ to $t_j$
+ Find a MST $F$ in $H$
+ Replace each edge in $F$ by the corresponding path in $G$ (deleting cycle)
#### Analysis
+ $F^*$ is the optimal Steiner tree in $G$
+ Duplicate each edge in $F^*$: **all degrees are even**
+ Open up $F^*$ into a **Euler** cycle $Z$
    + $L(Z)=2L(F^*)$, where $L(S)$ is the total length of all edges in $S$
    ![](https://i.imgur.com/6Ucx00a.png)
+ $Z$ can be transformed into an **Euler tour** in $H$
    + For any $t,t'\in T$, $c_Z(t,t')\geq c_H(t,t')$
    + The Euler tour in $H$ is itself a Steiner tree in $H$
    + So $F$ we get is smaller than $Z$
    ![](https://i.imgur.com/rRPgeqJ.png)
+ So the approximation ratio is $2$
### Constrained Steiner Forest Problem
+ Input
    + Undirected graph $G=(V,E)$
    + Cost function: $c:E\to\Bbb R^+$
    + Disjoint sets $T_1,...,T_k\subseteq V$
+ Output
    + Minimum cost subgraph $H$ such that each set $T_i$ belongs to the same connected component of $H$
#### Integer Programming Formulation
+ Requirement function $f:S\to\{0,1\}$, $\forall S\subseteq V$
    + $f(S)=1$ if there is a set $T_i$ split between $S$ and $V\setminus S$ 
        + **the forest $H$ must cross the cut $S$**
    + $f(S)=0$ otherwise 
        + **no requirement, but maybe still a cut**
    + Note: $f(S)=f(V\setminus S)$, $f$ is a function on cuts
    ![](https://i.imgur.com/DRG5VQ3.png)

| $\min\sum_{e\in E}c_ex_e$ |
|---|
|s.t. $$\sum_{e\in\delta(S)}x_e\geq f(S), S\subseteq V$$ $$x_e\in\{0,1\}, e\in E$$|
+ $\delta(S)$ is the edges that cross the cut $S$
    ![](https://i.imgur.com/06tFDcK.png)
#### Linear Programming Relaxation and Dual Problem
| $\min\sum_{e\in E}c_ex_e$ | $\max\sum_{S\subseteq V}f(S)y_S$ |
|---|---|
|s.t. $$\sum_{e\in\delta(S)}x_e\geq f(S), S\subseteq V\\x_e\geq 0, e\in E$$|s.t. $$\sum_{S:e\in\delta(S)}y_s\leq c_e, e\in E\\y_S\geq 0, S\subseteq V$$|
+ Note the we may have exponential number of $y$-values, but primal-dual algorithm still works since only a polynomial number of them are non-zero
#### Primal-Dual Algorithm
+ Primal complementary slackness
    + For all $e\in E$, $x_e=0$ or $\sum_{S|e\in\delta(S)}y_S=c_e$
    + So $x_e=1\Rightarrow\sum_{S|e\in\delta(S)}y_S=c_e$, that is, **every picked edge must be tight**
+ **No strict dual conditions (only an approximate algorithm)**
+ **Because most $y_S$ are $0$**
##### Definition
+ Picked edge: those $e$ such that $x_e=1$
+ A set $S$ is **active** during the algorithm iff
    + It is a **connected component** in the current picked forest
    + $f(S)=1$ (to be expanded)
+ So we raise the $y_S$ for active set $S$ until new tight edges emerge
    + Tight edge $e$: $\sum_{S|e\in\delta(S)}y_S=c_e$
    ![](https://i.imgur.com/RvtWP0W.png)
##### Algorithm
:::info
+ $F\leftarrow\emptyset,y_S\leftarrow 0$ for all $S\subseteq V$
+ **while** there is an active set **do**
    + Simultaneously raise $y_S$ for all active sets $S$, until some $e$ goes tight
    + $F\leftarrow F\cup\{e\}$
+ Prune **redundant** edges in $F$
:::
![](https://i.imgur.com/ZITAsFn.png)
+ Example:
    + We want to connect $\{s,t\}$ and $\{u,v\}$
    ![](https://i.imgur.com/o8Cp8D4.png)
    ![](https://i.imgur.com/9kWwwCx.png)
    ![](https://i.imgur.com/YSwT9qq.png)
    ![](https://i.imgur.com/cOjoFAi.png)
    ![](https://i.imgur.com/GdfGlac.png)
    + Finally
    ![](https://i.imgur.com/9bKZmdQ.png)
:::info
Prune **redundant** edges in $F$
+ For all edges $e$ in $F$ **in the reverse order they added to $F$** do
    + If **$F\setminus\{e\}$ is a feasible solution** then
        + Remove $e$ from $F$
:::
##### Analysis
+ No cut $S$ with $f(S)=0$ is raised during the algorithm, so $f(S)=0\Rightarrow y_S=0$
+ So $\sum_{S\subseteq V}y_S=\sum_{S\subseteq V}f(S)y_S$
+ We want to show $\sum_{e\in F}c_e\leq 2\sum_{S\subseteq V}y_S$, **so it’s a $2$-approximation** (WHY?)
    + Since it’s a relaxation, so the solution of the original LP $\geq$ the solution of the relaxed LP, so if $\sum_{e\in F}c_e$ is a $2$-approx. for this LP, it a $2$-approx. of the original IP
+ Let $deg_F(S)$ be the number of edges of $F$ crossing the cut $S$, then $\sum_{e\in F}c_e=\sum_{S\subseteq V}deg_F(S)y_S$
    + Since $\sum_{e\in F}c_e=\sum_{e\in F}(\sum_{S:e\in\delta(S)}y_S)=\sum_{S\subseteq V}(\sum_{e\in\delta(S)\cap F}y_S)$
    ![](https://i.imgur.com/WfdG8jd.png)
+ When we raise all active sets by $\Delta$ ($\sum_{e\in F}c_e\leq 2\sum_{S\subseteq V}y_S$)
    + LHS increases by $2\Delta\times$(#active sets)
    + RHS increases by $\Delta\times(\sum_{S\ active}deg_F(S))$
    + Need to show $\sum_{S\ active}deg_F(S)/$(#active sets)$\leq 2$
        + Key observation: current inactive sets cannot be leaves! Otherwise the edge in $F$ connecting to it will be deleted in the pruning step
        + So average degree of active sets is at most $2$
        ![](https://i.imgur.com/AUxd6zf.png)
#### Examples of Requirement Functions
+ Steiner tree: for any cut $S$ separating terminals, $f(S)=1$
+ Shortest path between $s$ and $t$: for any cut $S$ separating $s$ and $t$, $f(S)=1$
+ Minimum weight perfect matching: $f(S)=1$ iff $|S|$ is odd (At least one vertex is matched outside $S$)


## Feedback Vertex Set
### Problem Definition
+ Input: A directed graph $G=(V,E)$ and nonnegative weights $w_i>0$ for $i\in V$
+ Problem: Find a set $S\subseteq V$ of **minimum weight** such that $G[V\setminus S]$ is a forest
![](https://i.imgur.com/JAIogOQ.png)
### LP Formulation
+ We simply write the constraints based on all cycles $C\in\mathcal C$ have a node in the feedback set

|$\min \sum_{i\in V}w_ix_i$|
|---|
|s.t. $$\sum_{i\in C}x_i\geq 1, \forall C\in\mathcal C\\x_i\in\{0,1\},\forall i\in V$$|

+ LP relaxation and dual problem

|Primal|Dual|
|---|---|
|$\min \sum_{i\in V}w_ix_i$|$\max\sum_{C\in\mathcal C}y_C$
|s.t. $$\sum_{i\in C}x_i\geq 1, \forall C\in\mathcal C\\x_i\geq 0,\forall i\in V$$|s.t. $$\sum_{C\in\mathcal C:i\in C}y_C<w_i,\forall i\in V\\y_C\geq 0,\forall C\in\mathcal C$$|
#### Algorithm
:::info
+ $y\leftarrow 0$
+ $S\leftarrow\emptyset$
+ **while** there exists a cycle $C$ in $G$ **do**
    + Increase $y_C$ until there is some $\ell\in V$ such that $\sum_{C'\in\mathcal C:i\in C}y_C'=w_\ell$
    + $S\leftarrow S\cup \{\ell\}$
    + Remove $\ell$ from $G$
    + Repeatedly remove vertices of degree one from $G$
+ return $S$
:::
#### Analysis
+ The final **vertices** in $S$ we get are all tight $\sum_{C:i\in C}y_C=w_i,\forall i\in S$
    + Because after include $i$ in $S$, the $y_C$ for cycles containing it will not change any more
+ Approximation ratio
    + Weight: $\sum_{i\in S}w_i=\sum_{i\in S}\sum_{C:i\in C}y_C=\sum_Cy_C|S\cap C|$
    + **But still no bound on $|S\cap C|$ (for those $y_C>0$)**
### Improvement
+ Observation: For any path $P$ of vertices of degree two in graph $G$, our algorithm will choose at most one vertex from $P$
    + Because they must be in one cycle
    + When we choose one vertex in $P$, others will be deleted one by one because they have degree one 
    ![](https://i.imgur.com/nSayvdw.png)
#### Theorem: In any graph $G$ that has no vertices of degree one, there is a cycle with at most $2\lfloor\log_2 n\rfloor$ vertices of degree three or more, and it can be found in linear time
+ Run a BFS in $G$, the worst-case is 
![](https://i.imgur.com/UmVu5PB.png)
#### Algorithm
:::info
+ $y\leftarrow 0$
+ $S\leftarrow\emptyset$
+ Repeatedly remove vertices of degree one from $G$ 
+ **while** there exists a cycle $C$ in $G$ **do**
    + Find cycle $C$ with at most $2\lfloor\log_2 n\rfloor$ vertices of degree three or more
    + Increase $y_C$ until there is some $\ell\in V$ such that $\sum_{C'\in\mathcal C:i\in C}y_C'=w_\ell$
    + $S\leftarrow S\cup \{\ell\}$
    + Remove $\ell$ from $G$
    + Repeatedly remove vertices of degree one from $G$
+ return $S$
:::
#### Analysis
+ Approximation ratio
    + Weight: $\sum_{i\in S}w_i=\sum_{i\in S}\sum_{C:i\in C}y_C=\sum_Cy_C|S\cap C|$
+ Bound on $|S\cap C|\leq 4\lfloor\log_2 n\rfloor$
    + When we increase the $y_C$ for some cycle $C$, since there are at most $2\lfloor\log_2 n\rfloor$ vertices in it of degree $\geq 3$
    + There are at most $2\lfloor\log_2 n\rfloor$ subpaths of degree-$2$ vertices joining them, we only need to include one per subpath in $S$ 
    + In total: $4\lfloor\log_2 n\rfloor$