This is the lecture notes from Chandra Chekuri's CS583 course on Approximation Algorithms. Chapter 12: Primal Dual for Constrained Forest Problems.
You can read Chapter 13: Survivable Network Design Problem, here. Chapter 11: Steiner Forest Problem, here.
Chapter 12
We previously saw a primal-dual based 2-approximation for the Steiner Forest problem. The algorithm can be generalized to a much wider class of problems that involve finding a min-cost forest in an undirected edge-weighted graph that needs to satisfy some constraint. The resulting machinery is a more abstract and requires more advanced tools. We start with some problems all of which are NP-Hard.
Point to point connection problem: Given edge-weighted graph G=(V,E)G=(V, E) and two disjoint sets X={s_(1),dots,s_(k)}X=\left\{s_{1}, \ldots, s_{k}\right\} and Y={t_(1),dots,t_(k)}Y=\left\{t_{1}, \ldots, t_{k}\right\} of terminals find the min-cost forest in GG such that each connected component contains same number of terminals from XX and YY.
Lower Capacitated Tree Problem: Given G=(V,E),c:E rarrR^(+)G=(V, E), c: E \rightarrow \mathbb{R}^{+} and a k inZ^(+)k \in \mathbb{Z}^{+} find a set E^(')sube EE^{\prime} \subseteq E of minimum cost such that every connected component in (V,E^('))\left(V, E^{\prime}\right) has at least kk edges.
Connectivity Augmentation: Given an undirected kk-edge connected graph G=(V,E)G=(V, E) and a set of edges E^("aug ")sube V xx V-EE^{\text {aug }} \subseteq V \times V-E, find a set E^(')subeE^("aug ")E^{\prime} \subseteq E^{\text {aug }} of minimum cost such that G=(V,E uuE^('))G=\left(V, E \cup E^{\prime}\right) is (k+1)(k+1)-edge connected.
Steiner Connectivity Augmentation: Let G=(V,E)G=(V, E) be an edge-weighted graphs and let (s_(1),t_(1)),dots,(s_(h),t_(h))\left(s_{1}, t_{1}\right), \ldots,\left(s_{h}, t_{h}\right) be kk pairs such that each pair is kk-edgeconnected in GG. Given a set of edges E^("aug ")sube V xx V-EE^{\text {aug }} \subseteq V \times V-E, find a set E^(')subeE^("aug ")E^{\prime} \subseteq E^{\text {aug }} of minimum cost such that in G^(')=(V,E uuE^('))G^{\prime}=\left(V, E \cup E^{\prime}\right) each pair (s_(i),t_(i))\left(s_{i}, t_{i}\right) is (k+1)(k+1)-edge connected.
Each of the preceding problems can be cast as a special case of the following abstract problem. Given an edge-weighted graph G=(V,E)G=(V, E) and a function f:2^(V)rarr{0,1}f: 2^{V} \rightarrow\{0,1\}, find a min-cost subset of edges E^(')E^{\prime} such that |delta_(E^('))(S)| >= f(S)\left|\delta_{E^{\prime}}(S)\right| \geq f(S) for each S sube VS \subseteq V. We use the notation delta_(F)(S)\delta_{F}(S) to denote the edges from an edge set FF that cross the set/cut SS. Alternatively we want a min-cost subset of edges E^(')E^{\prime} such that each set S inSS \in \mathcal{S} is crossed by an edge of E^(')E^{\prime} where S={S∣f(S)=1}\mathcal{S}=\{S \mid f(S)=1\}. It is easy to observe that a minimal solution to this abstract problem is a forest since any cut needs to be covered at most once. This formulation is too general since ff may be completely arbitrary. The goal is to find a sufficiently general class that captures interesting problems while still being tractable. The advantage of {0,1}\{0,1\} functions is precisely because the minimal solutions are forests. We will later consider integer valued functions.
Definition 12.1.Given a graph G=(V,E)G=(V, E) and an integer valued function f:2^(V)rarrZf: 2^{V} \rightarrow \mathbb{Z} we say that a susbet of edges FF is feasible for ff or covers ff iff |delta_(F)(S)| >= f(S)\left|\delta_{F}(S)\right| \geq f(S) for all S sube VS \subseteq V.
Remark 12.1. Even though it may seem natural to restrict attention to requirement functions that only have non-negative entries, we will see later that the flexibility of negative requirements is useful.
Given a network design problem Pi\Pi in an undirected graph G=(V,E)G=(V, E) and an integer valued function f:2^(V)rarrZ_(+)f: 2^{V} \rightarrow \mathbb{Z}_{+} we say that the requirement function of Pi\Pi is ff if covering ff is equivalent to satisfing the constraints of Pi\Pi.
12.1 Classes of Functions and Setup
Here we consider classes of requirement functions f:2^(V)rarrZf: 2^{V} \rightarrow \mathbb{Z} and their relationship. Even though we define more generally, for this chapter the focus will be on {0,1}\{0,1\} functions.
Definition 12.2.ffis maximal if for all disjoint AA and BB we have f(A uu B) <=f(A \cup B) \leqmax{f(A),f(B)}\max \{f(A), f(B)\}.
Exercise 12.1. Prove that the requirement function of Steiner Forest is maximal.
Definition 12.3.ffis proper if it is symmetric, maximal and f(V)=0f(V)=0.
Exercise 12.2. Prove that the requirement function of Steiner Forest is proper.
Exercise 12.3. Prove that the requirement function Steiner Connectivity Augmentation is proper.
Definition 12.4.ffis downward monotone if f(A) <= f(B)f(A) \leq f(B)for allO/!=B sub A\emptyset \neq B \subset A.
Exercise 12.4. Prove that the requirement function of the Lower Capacitated Tree problem as downward monotone.
A very general class is the one given below.
Definition 12.5.ffis skew-supermodular (also called weakly-supermodular) if for all AA and BB one of the following conditions hold,
1.f(A)+f(B) <= f(A uu B)+f(A nn B)f(A)+f(B) \leq f(A \cup B)+f(A \cap B)
A specialization of skew-supermodular for {0,1}\{0,1\} functions will be the focus of this chapter.
Definition 12.6.A {0,1}\{0,1\} valued ff is uncrossable if for all AA and BB such that f(A)f(A) and f(B)=1f(B)=1, one of the following conditions hold,
1.f(A uu B)=1f(A \cup B)=1andf(A nn B)=1f(A \cap B)=1
2. f(A-B)=1f(A-B)=1andf(B-A)=1f(B-A)=1.
Claim 12.1.1.If ff is downward monotone then it is skew-supermodular.
Proof. Since ff is downward monotone, A-B sub AA-B \subset A and B-A sub BB-A \subset B we get:
and hence the second condition of skew-supermodularity always holds.
Lemma 12.1.If ff is proper then it is skew-supermodular.
Proof. Consider two sets A,BA, B. By considering AA as disjoint union of A-BA-B and A nn BA \cap B we have (i)f(A) <= max{f(A-B),f(A nn B)}(i) f(A) \leq \max \{f(A-B), f(A \cap B)\}. Similarly (ii) f(B) <=f(B) \leqmax{f(B-A),f(A nn B)}\max \{f(B-A), f(A \cap B)\}.
Now we apply symmetry of ff and note that f(A)=f(V-A)f(A)=f(V-A). Write V-AV-A as disjoint union of B-AB-A and V-(A uu B)V-(A \cup B). Hence (iii) f(A)=f(V-A) <=f(A)=f(V-A) \leqmax{f(B-A),f(V-(A uu B)}=max{f(B-A),f(A uu B)}\max \{f(B-A), f(V-(A \cup B)\}=\max \{f(B-A), f(A \cup B)\} where we used symmetry of ff in the second equality. Similary, (iv) f(B) <= max{f(A-B),f(A uu B}f(B) \leq \max \{f(A-B), f(A \cup B\}.
Summing up the four inequalities and replacing max{x,y}\max \{x, y\} by (x+y)//2(x+y) / 2 we obtain
2(f(A)+f(B)) <= f(A-B)+f(B-A)+f(A nn B)+f(A uu B)2(f(A)+f(B)) \leq f(A-B)+f(B-A)+f(A \cap B)+f(A \cup B)
which implies that f(A)+f(B) <= f(A-B)+f(B-A)f(A)+f(B) \leq f(A-B)+f(B-A) or f(A)+f(B) <= f(A nnf(A)+f(B) \leq f(A \capB)+f(A uu B)B)+f(A \cup B).
Definition 12.7.Let G=(V,E)G=(V, E) and f:2^(V)rarrZf: 2^{V} \rightarrow \mathbb{Z}. For each X sube EX \subseteq E, the residual requirement function f_(X):2^(V)rarrZf_{\mathrm{X}}: 2^{V} \rightarrow \mathbb{Z} is defined as:
Exercise 12.5. Let g:2^(V)rarrRg: 2^{V} \rightarrow \mathbb{R} be a symmetric submodular function. Prove that gg satisfies posi-modularity:
g(A)+g(B) >= g(A-B)+g(B-A)quad AA A,B sube V.g(A)+g(B) \geq g(A-B)+g(B-A) \quad \forall A, B \subseteq V .
Lemma 12.2.If ff is skew-supermodular then f_(X)f_{\mathrm{X}} is also skew-supermodular for any X sube EX \subseteq E.
Proof. The function |delta_(X)(.)|\left|\delta_{X}(.)\right| is submodular. Hence
|delta_(X)(A)|+|delta_(X)(B)| >= |delta_(X)(A nn B)|+|delta_(X)(B uu A)|quad AA A,B sube V.\left|\delta_{X}(A)\right|+\left|\delta_{X}(B)\right| \geq\left|\delta_{X}(A \cap B)\right|+\left|\delta_{X}(B \cup A)\right| \quad \forall A, B \subseteq V .
The function is also symmetric and hence also satisfies posi-modularity. Therefore,
|delta_(X)(A)|+|delta_(X)(B)| >= |delta_(X)(A-B)|+|delta_(X)(B-A)|quad AA A,B sube V.\left|\delta_{X}(A)\right|+\left|\delta_{X}(B)\right| \geq\left|\delta_{X}(A-B)\right|+\left|\delta_{X}(B-A)\right| \quad \forall A, B \subseteq V .
Now consider the function f_(X)f_{X} and let A,BA, B be any two subsets of VV. Suppose f(A)+f(B) >= f(A uu B)+f(A nn B)f(A)+f(B) \geq f(A \cup B)+f(A \cap B). Then
Similarly, if f(A)+f(B) >= f(A-B)+f(B-A)f(A)+f(B) \geq f(A-B)+f(B-A) we can use posi-modularity of |delta_(X)(*)|\left|\delta_{X}(\cdot)\right| to argue that f_(X)(A)+f_(X)(B) >= f_(X)(A-B)+f_(X)(B-A)f_{X}(A)+f_{X}(B) \geq f_{X}(A-B)+f_{X}(B-A). We note that |delta_(X)|\left|\delta_{X}\right| is both submodular and posi-modular which allows us to use the right inequality.
Remark 12.2. Allowing allow negative requirements in the definitoin of skewsupermodularity allows a clean proof when subtracting |delta_(X)(*)|\left|\delta_{X}(\cdot)\right|.
In the case of {0,1}\{0,1\} functions we make the following claim and leave the proof as an exercise which is similar to the the one above.
Lemma 12.3.Let f:2^(V)rarr{0,1}f: 2^{V} \rightarrow\{0,1\} be an uncrossable function and let X sube EX \subseteq E. Let h:2^(V)rarr{0,1}h: 2^{V} \rightarrow\{0,1\} be the residular function where h(S)=1h(S)=1 iff |delta_(X)(S)|=0\left|\delta_{X}(S)\right|=0. Then hh is uncrossable.
Definition 12.8.Let ff be a{0,1}a\{0,1\} requirement function over VV and let X sube EX \subseteq E. A set SS is violated with respect to XX if f_(X)(S)=1f_{X}(S)=1 (in other words SS is not yet covered by the edge set XX). A set SS is a minimal violated set if there is no S^(')⊊SS^{\prime} \subsetneq S such that S^(')S^{\prime} is violated.
Lemma 12.4.Let ff be an uncrossable function and X sube EX \subseteq E, then the minimial violated sets of ff with respect to XX are disjoint. That is, if A,BA, B are minimal violated sets then A=BA=B or A nn B=O/A \cap B=\emptyset.
Proof. Since f_(X)f_{\mathrm{X}} is also uncrossable it sufficies to consider minimal violated sets A,BA, B with respect to ff (hence the empty set of edges). Suppose the property does not hold. Then we can assume that A,BA, B propertly cross, that is, A-B,A nn B,B-AA-B, A \cap B, B-A are all non-empty. We have f(A)=f(B)=1f(A)=f(B)=1 since both are violated. Since ff is uncrossable, we have f(A-B)=f(B-A)=1f(A-B)=f(B-A)=1 or f(A nn B)=f(A uu B)=1f(A \cap B)=f(A \cup B)=1. In both cases we see that we violate minimality of A,BA, B.
12.2 A Primal-Dual Algorithm for Covering Uncrossable Functions
In this section we consider the following problem. Given a graph G=(V,E)G=(V, E) with non-negative edge weights c:E rarrR_(+)c: E \rightarrow \mathbb{R}_{+}and a uncrossable function f:2^(V)rarr{0,1}f: 2^{V} \rightarrow\{0,1\} find a min-cost set of edges F sube EF \subseteq E such that |delta_(F)(S)| >= f(S)\left|\delta_{F}(S)\right| \geq f(S) for all SS. An important computational issue is how ff is specified. A natural model is to consider the value oracle one where we have access to f(S)f(S) via an oracle. Given S sube VS \subseteq V, the oracle returns f(S)f(S). However this is not sufficient in the general context of uncrossable functions as we see from the following example. Fix some set AA. Define the function f_(A)f_{A} where f_(A)(S)=1f_{A}(S)=1 iff S=AS=A. It is easy to see that there is a feasible solution iff delta_(E)(A)!=O/\delta_{E}(A) \neq \emptyset. How do we even verify that there is a feasible solution via a value oracle? In general it may take an exponential number of queries to find AA. Hence we need more. We will assume that there is an oracle that given GG and X sube EX \subseteq E outputs the set of all minimal violated sets of f_(X)f_{X}. This will typically be easy to ensure for specific functions of interest. We note that for some special class of functions such as proper functions, a value oracle suffices to find the minimal violated sets.
We write the primal and dual LPs for covering ff via edges of a given graph G=(V,E)G=(V, E).
{:["min"sum_(e in E)c_(e)x_(e)],["such that"sum_(e in delta(S))x_(e) >= f(S)quad AA S sube V],[x_(e)in0quad AA e in E],[]:}\begin{aligned}
\text {min} &&& \sum_{e \in E} c_{e} x_{e} \\
\text {such that} &&& \sum_{e \in \delta(S)} x_{e} \geq f(S) \quad \forall S \subseteq V \\
&&& x_{e} \in 0 \quad \forall e \in E
\\
\\
\end{aligned}
{:["min"sum_(S inS)f(S)y_(S)],["such that"sum_(S:e in delta(S))y_(S) <= c_(e)quad AA e in E],[y_(S) >= 0quad AA S sube V]:}\begin{aligned}
\text {min} &&& \sum_{S \in \mathcal{S}}f(S) y_{S} \\
\text {such that} &&& \sum_{S: e \in \delta(S)} y_{S} \leq c_{e} \quad \forall e \in E \\
&&& y_{S} \geq 0 \quad \forall S \subseteq V
\end{aligned}
The primal-dual algorithm is similar to the one for Steiner Forest with a growth phase and reverse-delete phase.
qquad\qquad Let C_(1),C_(2),dots,C_(ℓ)C_{1}, C_{2}, \ldots, C_{\ell} be minimally violated sets of ff with respect to FF
qquad\qquad Raise y_(C_(i))y_{C_{i}} for 1 <= i <= ℓ1 \leq i \leq \ell uniformly until some edge ee becomes tight
qquad F larr F+e\qquad F \leftarrow F+e
qquadx_(e)=1\qquad x_{e}=1
quad\quad Let F^(')={e_(1),e_(2),dots,e_(t)}F^{\prime}=\left\{e_{1}, e_{2}, \ldots, e_{t}\right\} where e_(i)e_{i} is edge added to FF in iteration ii
quadF^(')=F\quad F^{\prime}=F
quad\quad for i=ti=t down to 11 do
qquad\qquad if (F^(')-e_(i))\left(F^{\prime}-e_{i}\right) is feasible then F^(')=F^(')-e_(i)F^{\prime}=F^{\prime}-e_{i}
quad\quad Output F^(')F^{\prime}
Analysis: We can prove the following by induction on the iterations and omit the routine details.
Lemma 12.5.The output of the algorithm, F^(')F^{\prime}, is a feasible solution that covers ff. Assuming oracle access to finding the minimal violated sets in each iteration, the algorithm can be implemented in polynomial time.
The preceding lemma shows that the algorithm correctly outputs a feasible solution. The main part is to analyze the cost of the solution.
Theorem 12.9.Let F^(')F^{\prime} be the output of the algorithm. Then c(F^(')) <= 2sum_(S)f(S)y_(S)c\left(F^{\prime}\right) \leq 2 \sum_{S} f(S) y_{S} and hence c(F^(')) <= 2"OPT"c\left(F^{\prime}\right) \leq 2\text{OPT}.
The cost analysis is based on the following key structural lemma.
Lemma 12.6.Let G=(V,E)G=(V, E) be a graph and let f:2^(V)rarr{0,1}f: 2^{V} \rightarrow\{0,1\} be an uncrossable function and let C\mathcal{C} be the set of minimal violated sets of ff with respect with respect to O/\emptyset. Let F sube EF \subseteq E be any minimal feasible solution that covers ff. Then sum_(C inC)deg_(F)(C) <= 2|C|\sum_{C \in \mathcal{C}} \operatorname{deg}_{F}(C) \leq 2|\mathcal{C}| where deg_(F)(C)=|delta(C)nn F|\operatorname{deg}_{F}(C)=|\delta(C) \cap F| is the number of edges of FF crossing CC.
We defer the proof of the preceding lemma to the following subsection and finish the analysis of the 2-approximation. This is similar to the one for Steiner Forest. Let tt be the number of iterations of the algorithm. Let C_(i)\mathcal{C}_{i} be the minimal violated sets in iteration ii of the algorithm and let Delta_(i)\Delta_{i} be the amount by which the duals grow in iteration ii. We call any C inC_(i)C \in \mathcal{C}_{i}active in iteration ii. We have sum_(e inF^('))c_(e)=sum_(e inF^('))sum_(S:e in delta(S))y_(S)\sum_{e \in F^{\prime}} c_{e}=\sum_{e \in F^{\prime}} \sum_{S: e \in \delta(S)} y_{S} since we add edges to FF only when the dual constraint is tight and F^(')sube FF^{\prime} \subseteq F. We also observe that the duals are grown only for sets S sube VS \subseteq V where f(S)=1f(S)=1 and hence sum_(S)f(S)y_(S)=sum_(S)y_(S)\sum_{S} f(S) y_{S}=\sum_{S} y_{S} for the dual solution created by the algorithm.
To complete the analysis we need the following lemma which can be seen as a corollary of Lemma 12.6.
Lemma 12.7.Consider any iteration ii of the algorithm. Thensum_(C inC_(i))deg_(F^('))(C) <= 2|C_(i)|\sum_{C \in \mathcal{C}_{i}} \operatorname{deg}_{F^{\prime}}(C) \leq 2\left|\mathcal{C}_{i}\right|.
Proof. Consider iteration ii. Let X={e_(1),e_(2),dots,e_(i-1)}X=\left\{e_{1}, e_{2}, \ldots, e_{i-1}\right\} which are the set of edges added by algorithm in the growth phase prior to iteration ii. Thus C_(i)\mathcal{C}_{i} is the minimal violated sets with respect to XX. Consider the graph G^(')=(V,E\\X)G^{\prime}=(V, E \backslash X) and the function f_(X)f_{X}. We observe that F^('')=F^(')\\XF^{\prime \prime}=F^{\prime} \backslash X is a minimal feasible solution to covering f_(X)f_{X} in G^(')-G^{\prime}- this is because of the reverse delete process. Moreover we claim that deg_(F^('))(C)=deg_(F^(''))(C)\operatorname{deg}_{F^{\prime}}(C)=\operatorname{deg}_{F^{\prime \prime}}(C) for any C inC_(i)C \in \mathcal{C}_{i} (why?). We can now apply Lemma 12.612.6 to the function f_(X)f_{X} (which is uncrossable) and G^(')G^{\prime} and F^('')F^{\prime \prime} so obtain:
Since FF is a minimal feasible solution to cover ff, for every e in Fe \in F there must be a set S_(e)S_{e} such that f(S_(e))=1f\left(S_{e}\right)=1 and delta_(F)(S_(e))={e}\delta_{F}\left(S_{e}\right)=\{e\}; this is the reason we cannot remove ee from FF and maintain feasibility. We call such a set S_(e)S_{e} a witness set for ee. Clearly a witness set S_(e)S_{e} is a violated set.
Claim 12.2.1.Let S_(e)S_{e} be a witness set for e in Fe \in F. Then for any minimal violated set CC we have C subeS_(e)C \subseteq S_{e} or C nnS_(e)=O/C \cap S_{e}=\emptyset.
Proof. If CC crosses S_(e)S_{e} then either C-S_(e)C-S_{e} or C nnS_(e)C \cap S_{e} would also be violated (since ff is uncrossable) contradicting minimality of CC.
Note that there can be many witness sets for the same edge, however, the same set cannot be a witness set for two different edges.
Definition 12.10.Given a minimal feasible solution FF we call a family of sets S\mathcal{S} a witness family for FF if there is a bijection h:F rarrSh: F \rightarrow \mathcal{S} such that h(e)h(e) is a witness set for ee.
Given FF we can construct a witness family by considering each edge e in Fe \in F and picking an arbitrary witness set for ee and additing it to the collection.
Definition 12.11.A family S\mathcal{S} of finite sets is laminar if no two sets A,B inSA, B \in \mathcal{S} cross.
We have seen that there is a witness family for FF since it is minimal. We can obtain a special witness family starting with an arbitrary witness family.
Lemma 12.8.There is a witness family for FF which is laminar.
Proof. The process is based on uncrossing. Suppose we start with an arbitrary witness family S\mathcal{S} and it is not laminar. Let S_(e_(1)),S_(e_(1))S_{e_{1}}, S_{e_{1}} be the witness sets for e_(1),e_(2)in Fe_{1}, e_{2} \in F such that S_(e_(1)),S_(e_(2))S_{e_{1}}, S_{e_{2}} cross.
Claim 12.2.2.One of the following holds: (i) (S\\{S_(e_(1)),S_(e_(2))})uu{S_(e_(1))-S_(e_(2)),S_(e_(2))-S_(e_(1))}\left(\mathcal{S} \backslash\left\{S_{e_{1}}, S_{e_{2}}\right\}\right) \cup\left\{S_{e_{1}}-S_{e_{2}}, S_{e_{2}}-S_{e_{1}}\right\} is a witness family for FF (ii) (S\\{S_(e_(1)),S_(e_(2))})uu{S_(e_(1))nnS_(e_(2)),S_(e_(2))uuS_(e_(2))}\left(\mathcal{S} \backslash\left\{S_{e_{1}}, S_{e_{2}}\right\}\right) \cup\left\{S_{e_{1}} \cap S_{e_{2}}, S_{e_{2}} \cup S_{e_{2}}\right\} is a witness family for FF.
The new sets don't cross each other but what about other sets in the family? One can argue that the number of crossing can only decrease. More formally, suppose we have three sets A,B,DA, B, D and say DD crosses pp sets from A,BA, B(pp is one of {0,1,2}\{0,1,2\}). If we uncross A,BA, B (that is replace A,BA, B by A-B,B-AA-B, B-A or A nn B,A uu BA \cap B, A \cup B) then the number of sets that DD crosses after uncrossing cannot increase. We leave this claim as an exercise. This means that repeated uncrossing of two crossing sets will eventually lead to a laminar family.
Now we prove the claim. S_(e_(1)).S_(e_(1))S_{e_{1}} . S_{e_{1}} and S_(e_(2))S_{e_{2}} are violated sets which means that f(S_(e_(1)))=1f\left(S_{e_{1}}\right)=1 and f(S_(e_(2)))=1f\left(S_{e_{2}}\right)=1. Since ff is uncrossable, say f(S_(e_(1))-S_(e_(2)))=1f\left(S_{e_{1}}-S_{e_{2}}\right)=1 and f(S_(e_(2))-S_(e_(1)))=1f\left(S_{e_{2}}-S_{e_{1}}\right)=1. The only edges from FF that can cross S_(e_(1))-S_(e_(2))S_{e_{1}}-S_{e_{2}} and S_(e_(2))-S_(e_(1))S_{e_{2}}-S_{e_{1}} are e_(1)e_{1} and e_(2)e_{2} - if there is another edge ee that crosses one of them then it would also cross one of S_(e_(1))S_{e_{1}} and S_(e_(2))S_{e_{2}} and hence they would not be witness sets. Since F^(')F^{\prime} is a feasible solution, S_(e_(1))-S_(e_(2))S_{e_{1}}-S_{e_{2}} and S_(e_(2))-S_(e_(1))S_{e_{2}}-S_{e_{1}} are both crossed by some edge from Y={e_(1),e_(2)}Y=\left\{e_{1}, e_{2}\right\}. We claim that each of them is crossed by exactly one of them. If this is the case then they are valid witness sets for the two edges e_(1),e_(2)e_{1}, e_{2}. To see why exaclty one of them crosses each set we use submodularity/posi-modularity:
The first inequality is since each is covered and the second inequality is because of posi-modularity of |delta_(Y)(*)|\left|\delta_{Y}(\cdot)\right|.
The other case when f(S_(e_(1))nnS_(e_(2)))=1f\left(S_{e_{1}} \cap S_{e_{2}}\right)=1 and f(S_(e_(1))uuS_(e_(2)))=1f\left(S_{e_{1}} \cup S_{e_{2}}\right)=1 can also be handled with a similar argument.
Let S\mathcal{S} be a laminar witness family for FF. We create a rooted tree PP from S\mathcal{S} as follows. To do this we first add VV to the family. For each set S inSS \in \mathcal{S} we add a vertex v_(S)v_{S}. For any S,TS, T such that TT is the smallest set in S\mathcal{S} containing SS we add the edge (v_(S),v_(T))\left(v_{S}, v_{T}\right) which makes v_(T)v_{T} the parent of v_(S)v_{S}. Since we added VV to the family we obtain a tree since every maximal set in the original family becomes a child of v_(V)v_{V}. Note that PP has |F||F| edges and |F|+1|F|+1 nodes and each e in Fe \in F corresponds to the edge (v_(S_(e)),v_(T))\left(v_{S_{e}}, v_{T}\right) of PP where v_(T)v_{T} is the parent of v_(S_(e))v_{S_{e}} in PP. We keep this bijection between FF and edges of PP in mind for later.
See figure.
Consider any minimal violated set C in CC \in C. We observe that CC cannot cross any set in S\mathcal{S} since it is a witness family. For each CC we associate the minimal set S inSS \in \mathcal{S} such that C sube SC \subseteq S. We call v_(S)v_{S} an active node of TT if there is a C inSC \in \mathcal{S} associated with it. Note that (i) not all nodes of PP may be active (ii) every CC is associated with exactly one active node of PP (iii) multiple sets from CC can be associated with the same active node of PP.
Lemma 12.9.Let P_(a)P_{a} be the active nodes of PP. Then |P_(a)| <= |C|\left|P_{a}\right| \leq|C| and every leaf of PP other than potentially the root is an active node.
Proof. Since each CC is associated with an active node we obtain |P_(a)| <= |C|\left|P_{a}\right| \leq|C|. A leaf of PP corresponds to a minimal set from S\mathcal{S} or the root. If S_(e)S_{e} is a minimal set from S\mathcal{S} then S_(e)S_{e} is a violated set and hence must contain a minimal violated set C. But then S_(e)S_{e} is active because of CC. Consider v_(V)v_{V}. If it is a leaf then it has only one child which is the unique maximal witness set SS. The root can be inactive since the function ff is not necessarily symmetric. (However, if ff is symmetric then V-SV-S would also be a violated set and hence contain a minimal violated set from CC.)
Figure 12.1: Laminar witness family for a minimal solution FF shown as red edges. Sets in green are the minimal violated sets and the sets in black are the witness sets. The root set VV is not drawn.
Lemma 12.10.Let v_(T)v_{T} be an active node in PP. Let C^(')subeC\mathcal{C}^{\prime} \subseteq \mathcal{C} be set of all minimal violated sets associated with v_(T)v_{T}. Then sum_(C inC^('))deg_(F)(C) <= deg_(P)(v_(T))\sum_{C \in \mathcal{C}^{\prime}} \operatorname{deg}_{F}(C) \leq \operatorname{deg}_{P}\left(v_{T}\right).
Proof. Let Y=uu_(C inC^('))delta_(F)(C)Y=\cup_{C \in \mathcal{C}^{\prime}} \delta_{F}(C) be the set of edges incident to the sets in C^(')\mathcal{C}^{\prime}. Consider any C inC^(').C sub TC \in \mathcal{C}^{\prime} . C \subset T and CC is also disjoint from the children of TT. Consider an edge e indelta_(F)(C)e \in \delta_{F}(C). If ee crosses TT then TT is the witness set for ee (since only one edge from FF can cross TT for which it is the witness) and we charge ee to the parent edge of TT. If ee does not cross TT then the witness set S_(e)S_{e} must be a child of TT. Since only one edge can cross each child of TT we can charge ee to one child of TT. Note that no edge e in Ye \in Y can be incident to two set C_(1),C_(2)inC^(')C_{1}, C_{2} \in \mathcal{C}^{\prime} since both one end point of ee must be contained in a child of TT (assuming ee does not cross TT) and both C_(1),C_(2)C_{1}, C_{2} are contained in TT and disjoint from the children of TT. See figure. Therefore, we can charge sum_(C inC^('))deg_(F^('))(C)\sum_{C \in \mathcal{C}^{\prime}} \operatorname{deg}_{F^{\prime}}(C) to the number of children of TT plus the parent edge of TT, which is deg_(P)(v_(T))\operatorname{deg}_{P}\left(v_{T}\right).
Now we are ready to finish the proof. From Lemma 12.10 and the fact that each C inCC \in \mathcal{C} is associated to some active node, we have
To bound sum_(v inP_(a))deg_(p)(v)\sum_{v \in P_{a}} \operatorname{deg}_{p}(v) we had observed that in the tree PP every leaf except perhaps the root node is an active node. Suppose root is an active node or it is not a leaf. Then from Lemma 11.2, sum_(v inP_(a))deg_(P)(v) <= 2|P_(a)|-2\sum_{v \in P_{a}} \operatorname{deg}_{P}(v) \leq 2\left|P_{a}\right|-2. Suppose root is a leaf and inactive. Again from Lemma 11.211.2 where we consider Z=P_(a)uu{v_(V)}Z=P_{a} \cup\left\{v_{V}\right\}, we have sum_(v inP_(a))deg_(P)(v)+1 <= 2|P_(a)+1|-2=2|P_(a)|\sum_{v \in P_{a}} \operatorname{deg}_{P}(v)+1 \leq 2\left|P_{a}+1\right|-2=2\left|P_{a}\right|. Hence sum_(v inP_(a))deg_(P)(v) <= 2|P_(a)|-1\sum_{v \in P_{a}} \operatorname{deg}_{P}(v) \leq 2\left|P_{a}\right|-1. Thus, in both cases we see that sum_(v inP_(a))deg_(P)(v) <= 2|P_(a)|\sum_{v \in P_{a}} \operatorname{deg}_{P}(v) \leq 2\left|P_{a}\right|. Finally we note that |P_(a)| <= |C|\left|P_{a}\right| \leq|\mathcal{C}| and hence putting together we have
Bibliographic Notes: The primal-dual algorithm for uncrossable function is from the paper of Williamson, Goemans, Mihail and Vazirani [1]. The proof in the paper assumes that hh is symmetric without explicitly stating it; for symmetric functions one obtains a slight advantage over 22. See Williamson's thesis [2] where he gives the proof for both symmetric and general uncrossable functions. The survey by Goemans and Williamson [3] describes the many applications of the primal-dual method in network design.
David P. Williamson, Michel X. Goemans, Milena Mihail, and Vijay V. Vazirani. “A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems”. In: 15 (1995), pp. 435–454. doi: http://dx.doi.org/10.1007/BF01299747. ↩︎
David P. Williamson. “On the design of approximation algorithms for a class of graphs problems”. PhD thesis. Cambridge, MA: MIT, 1993. ↩︎
Michel X Goemans and David P Williamson. “The primal-dual method for approximation algorithms and its application to network design problems”. In: Approximation algorithms for NP-hard problems (1997), pp. 144–191. ↩︎
A New Paradigm for Exploiting Pre-trained Model Hubs
A New Paradigm for Exploiting Pre-trained Model Hubs
It is often overlooked that the number of models in pre-trained model hubs is scaling up very fast. As a result, pre-trained model hubs are popular but under-exploited. Here a new paradigm is advocated to sufficiently exploit pre-trained model hubs.