COMP 5712 Introduction to Combinatorial Optimization

Just take the YES-certificate as an empty string, then the checking process just ignore the certificate and solve the problem using the polynomial-time algorithm by itself.

Consider the optimal Steiner tree of cost \(OPT\).

We double the edges in the tree. Then all the nodes have even degrees. Therefore, the graph have Eulerian tours. An Eulerian tour can be derived by running a DFS starting from an arbitrary node, at each node:

• Go to its neighbours that are not visited.
• Go back to its predecessor only if there is none

This Eulerian tour is of length exactly \(2 OPT\).

Now we construct a spanning tree of \(R\) in the tour: We record the order of nodes in \(R\) in which they firstly present in the tour \(r_1 \to r_2 \to \dots \to r_{|R|}\). Then paths on the tour \((r_1, \dots , r_2)\), \((r_2, \dots , r_3)\), … , \((r_{|R|}, \dots , r_1)\) comprise a partition of the tour, of total length \(2 OPT\). And the path \((r_1, r_2, \dots , r_{|R|})\) (edges connecting adjacent nodes exist) (drop \((r_{|R|}, r_1)\)) is a shortcut of these paths by the triangle inequality, of length at most \(2 OPT\) (a path is also a tree).

Therefore, the minimum spanning tree, which is smaller than this one, is of length at most \(2 OPT\).

\textbf{The reduction} basically constructs a new graph that satisfies the triangle inequality: Let the original graph be \(G\), we construct \(G'\) with a distance function \(d'\) in the following way: For any two points \(x\) and \(y\) in \(G\), let \(d'(x, y)\) be the length of the shortest path from \(x\) to \(y\) in \(G\). Then \(d'\) satisfies the triangle inequality: For every three points \(x, y, z\), the shorest path from \(x\) to \(y\) plus the one from \(y\) to \(z\) is \textbf{some} path from \(x\) to \(z\), so its length cannot be shortest than the length of the \textbf{shortest} path from \(x\) to \(z\), i.e., \(d'(x, z) \leq d'(x, y) + d'(y, z)\).

Then, we run the \(c\)-approximate algo. on \(G'\). Let the cost of the output solution be \(SOL(G')\), then \(SOL(G') \leq c \cdot OPT(G')\).

Next, we convert the solution to a solution to the original problem. We replace each edge \((x, y)\) in the solution by the shortest path from \(x\) to \(y\) in \(G\). At this stage, the total cost does not change. However, the converted solution may have duplicate edges and cycles, so we simply remove the duplicate edges, and take a MST of the remaining graph as the final solution. Clearly, the MST is a valid Steiner tree. It only removes edges, so \(MST \leq SOL(G') \leq c \cdot OPT(G')\).

By dropping an edge on an optimal TSP tour, we get \textbf{a} spanning path of the graph. So its cost must be \(\geq \) the MST. Therefore, \(OPT \geq MST\).

Similar to before, the shortcut TSP tour has cost \(SOL \leq 2 \cdot MST \leq 2 \cdot OPT\).

Consider the optimal TSP tour. We shortcut it (vertex set \(V\)) to form a tour (cycle) of \(S\) (\(\subseteq V\)). The cycle has weight \(C \leq OPT\).

Then we partition this cycle into two perfect matching of \(S\) by putting every two adjacent edges to different matchings. The sum of the weights of these two matchings is equal to \(C\), so the smaller weight among them must be \(\leq \frac{1}{2} C \leq \frac{1}{2} OPT\).

The min-weight perfect matching is smaller than or equal to this matching, so its weight is also \(\leq \frac{1}{2} OPT\).

By \(\mat{A} \vec{x} \leq \vec{b}\) and \(\vec{y} \geq \vec{0}\), we have \(\vec{y} ^{\intercal} \mat{A} \vec{x} \leq \vec{y} ^{\intercal} \vec{b}\). By \(\vec{y} ^{\intercal} \mat{A} \geq \vec{c} ^{\intercal}\) and \(\vec{x} \geq 0\), we have \(\vec{y} ^{\intercal} \mat{A} \vec{x} \geq \vec{c} ^{\intercal} \vec{x}\). Therefore, \(\vec{c} ^{\intercal} \vec{x} \leq \vec{b} ^{\intercal} \vec{y}\).

We assume that the primal LP is feasible and bounded.

The solution \(\vec{x}\) that achieves the maximum value must be at some intersection vertex of two constraints. Let us denote it by \(\vec{x}^{*}\), and the two constraints by \(\vec{a_i} \cdot \vec{x} \leq b_i\) and \(\vec{a_j} \cdot \vec{x} \leq b_j\), where \(\vec{a_i}\) and \(\vec{a_j}\)are the \(i\)-th and \(j\)-th rows of \(\mat{A}\) orthogonal to the constraint lines. These two are satisfied with equalities, i.e.,

Since the primal LP is bounded, the two constraint lines must form a triangle with some line orthogonal to \(\vec{c}\), so \(\theta_i + \theta_j < \pi\). Therefore, \(\vec{c}\) lies in the corner of \(\vec{a_i}\) and \(\vec{a_j}\), meaning that \(\vec{c}\) can be expressed as

As the notation \(y ^{*}\) indicates, \(y ^{*}\)’s are the multipliers of the constraints of the primal LP, and hence \(\vec{y}^{*}\) is a solution for the dual LP. More rigorously, we let \(y ^{*}_k = 0\) for \(k \neq i, j\) and check that \(\mat{A} ^{\intercal}\vec{y}^{*} = \vec{c} \geq \vec{c}\) and \(\vec{y}^{*} \geq \vec{0}\). \(\vec{y}^{*}\) is indeed a feasible solution for the dual.

The objective function value of the dual is

and the optimal value of the primal is

They are equal. Therefore, by the weak duality theorem, their optimal values are the same.

Validness (every edge is covered): We raise the charge of every edge until it has an endpoints selected into the VC. Thus, every edge is covered.

Approximation ratio: \(S\) and \(\vec{y}\) are the VC and the solution to the dual outputed by the above algorithm, respectively.

Validness: the same.

Approximation ratio: Let \(C\) be an arbitrary VC, and \(\vec{y}\) be the solution given by the above algorithm.

As proved before, \(w(S) \leq 2 \sum_{e \in E} y_{e}\). It suffices to show \(\sum_{e \in E} y_{e} \leq w(C ^{*})\) for an optimal VC \(C ^{*}\).

\textbf{Validness}: If some edge is not covered, then neither of its endpoints is selected into the VC. This is impossible.

\textbf{By direct combinatorial argument}: Any VC must cover the maximal matching \(M\). Since edges in \(M\) do not share common endpoints, any VC must use at least \(|M|\) vertices. Therefore the output has cost \(2 |M| \leq 2 \cdot OPT\).

\textbf{By the weak duality theorem}: A feasible solution to the dual is setting the charge of every edge in \(M\) to be \(1\), resulting in the total cost \(|M|\). By the WDT, \(|M|\) is a lower bound on the cost the optimal solution to the primal (VC).

\textbf{Expected cost}:

\textbf{The probability that \(u \in U\) is covered}:

It is easier to compute the probability that \(u\) is NOT covered: Assume \(u\) is covered by \(k\) sets, \(S_{i_1}, \dots , S_{i_{k}}\). Then

Alternatively, by \(1 - x \leq e ^{-x}\), we have \((1 - x_{i_1}^{*}) \cdots (1 - x_{i_{k}}^{*}) \leq e ^{-x_{i_1} ^{*} - \dots - x_{i_{k}} ^{*}} \leq e ^{-1}\).

So the probability that \(u\) IS covered is \(\geq 1 - \frac{1}{e}\).

collections by \(t\) (t for times).

\textbf{Probability that \(C'\) is valid}: Since it takes the union,

When \(t = c \ln |U|\), \(\prob (u \notin C') = \frac{1}{|U| ^{c}}\).

Then

When \(t = c \ln |U|\), \(\prob (C' \text{ is not valid}) \leq \frac{1}{|U| ^{c-1}}\). We can say \(C'\) is valid w.h.p.

\textbf{Expected cost}:

when \(t = c \ln |U|\), it is \(\leq (c \ln |U|) OPT\).

\textbf{Running time}: polynomial.

\(\E X \geq t \prob (X \geq t) + 0 \prob (X < t)\)

Here we show for \(O(\ln |U|) = 4 \cdot c \ln |U|\), where the constant \(c\) is from Thm~1.

\textbf{Running time}:

Let \(C'\) be the solution derived in each iteration. We first get some constant bounds for the two ``bad things’’:

• Validness: \(\prob (C' \text{ is not valid}) \leq \frac{1}{|U| ^{c-1}} \leq \frac{1}{4}\) when \(|U| \geq 2\) and \(c > 3\).
• Cost too large: By the Markov’s inequality, \(\prob [cost(C') \geq 4 \cdot c \ln |U| OPT_{LP}] \leq \frac{\E cost(C')}{4 \cdot c \ln |U| OPT_{LP}} = \frac{1}{4}\).

Therefore, the probability that either of them happens is \(\prob [\text{cost too high} \lor \text{SC not valid}] \leq \frac{1}{2}\) (by the union bound). Then the probability that both of them pass the check is \(\prob (\text{terminate}) \geq \frac{1}{2}\). The # iterations follow the Geometric distribution, so

Since each iteration (including the checking) can be done polynomial, the overall running time is expected to by polynomial.

\textbf{Approximation ratio}: guaranteed to be \(t\). (In this case, \(t = 4 \cdot c \ln |U|\)).

• \( \frac{1}{c_{j}}\) is the smallest to cover any uncovered element in \(D\).

The optimal solution covers \(D_{j}\), so it has cost at least \(|D_{j}| \cdot \frac{1}{c_{j}} \leq \frac{m-j+1}{c_{j}}\).

• Let \(D_{j}\) be the set of uncovered elements just before the step in which \(u_{j}\) is covered. Note that \(|D_{j}| \geq m-j+1\).

\(c_{j}\) is the largest # elements to be covered per unit of cost. The optimal solution covers \(D_{j}\). In the best case, every unit \(OPT_{SC}\) can cover \(c_{j}\) elements, so \(OPT_{SC} \cdot c_{j} \geq |D_{j}| \geq m-j+1\).

• Every set \(S_{i}\) of weight \(w_{i}\) cover at most \(c_{j} \cdot w_{i}\) elements.

Assign \(y_{u_1}, \dots , y_{u_{j-1}} = 0\), and \(y_{u_{j}}, \dots , y_{u_{m}} = \frac{1}{c_{j}}\). Check that for every set \(S_{i}\), \(\sum y_{u} = \frac{1}{c_{j}} \cdot |S_{i} \cap D_{j}| \leq \frac{1}{c_{j}} \cdot (c_{j} w_{i}) = w_{i}\).

The objective function value is \(|D_{j}| \cdot \frac{1}{c_{j}} \geq \frac{m-j+1}{c_{j}}\). By the weak duality theorem, this is a lower bound of \(OPT_{SC}\).

Let \(APX\) be the cost of the greedy solution. By the proposition above,

\(f(A)\) only involves flows across \(A\) and \(V - A\). To make use of the flow conservation, we consider completing all the flow out of and into \textit{nodes in \(A\)}.

Since flows within \(A\) are cancelled out,

Since flow are conserved at all nodes \(\in A\) except \(s\),

Thus, \(|f| = f(A)\).

By Lemma~1, \(|f| = f(A)\). By the definition of \(f(A)\),

Thus, \(|f| \leq c(A)\).

1. [1 to 2] By weak duality (corollary before).
2. [2 to 3] By contradiction. Suppose \(f\) is optimal but there is some augmenting path, then pushing this path will increase the flow value.

3. [\(\star\) 3 to 1] By construction. Let \(A\) be the set of vertices reachable from \(s\) in the residual network. Then, by definition, there is no edge (with positive capacity) from \(A\) to \(V - A\). This means that every edge \(e\) from \(A\) to \(V - A\) has flow \(f(e) = c(e)\) and every edge from \(V - A\) to \(A\) has flow \(0\). Thus,

   \begin{align*} f(A) = \sum_{a \in A, b \notin A} c(a, b) - \sum_{a \in A, b \notin A} 0 = c(A) \end{align*}

   Since \(|f| = f(A)\), we get \(|f| = c(A)\).

Stage 1: The goal is to achieve a total flow value of \(OPT \sim \frac{OPT}{2}\). Thus, before reaching the goal, \(OPT_{res} \in [\frac{OPT}{2}, OPT]\) and the fattest augmenting path has value \(\geq \frac{OPT /2}{2 |E|} = \frac{OPT}{4|E|}\). Hence, at most \(2|E|\) iterations are needed to reach the goal.

State \(i\): The goal is to achieve a flow value \(OPT \sim \frac{OPT}{2 ^{i}}\). So \(OPT_{res} \leq \frac{OPT}{2 ^{i}}\), the fattest augmenting path has value \(\geq \frac{OPT}{2 ^{i+1}|E|}\), and the number of iterations needed is \(\leq 2|E|\).

Since \(OPT\) is integral, the algorithm terminates in \(O(\log |OPT)\) stages. In each stage, there are \(O(|E|)\) iterations, each costing polynomial time (\(|E| \log |V|\)). So the total running time is \(O(poly \cdot |E| \log |OPT|)\).

We have argued that the fattest augmenting path has value \(\geq \frac{OPT_{res}}{2 |E|}\). For simplicity, we denote the \(OPT_{res}\) in the \(i\)-th iteration by \(res_{i}\). Since \(res_{i}\) equals \(res_{i-1}\) minus the value of the augmenting path, \(res_{i} \leq res_{i-1} \left( 1 - \frac{1}{2 |E|} \right)\).

By induction, this implies \(res_{i} \leq OPT \left( 1 - \frac{1}{2 |E|} \right) ^{i}\). Setting \(i = 2 |E| \log OPT\), we get \(res_{i} \leq OPT \cdot e ^{- \log OPT} = 1\). So the number of iterations is \(O(|E| \log |OPT|)\).

Consider the residual network after \(T\) iterations. Construct a BFS tree of the residual network starting at \(s\). We call \(V_0, V_1, \dots \) the vertices in the 0th, 1st layers etc. \(s\) is in \(V_0\) and \(t\) is in \(V_{l}\).

Note that a BFS tree has no downward edges that across more than \(1\) layers (no \((u, v)\) on the tree such that \(u \in V_{i}, v \in V_{j}, j - i > 1\)).

Suppose we pick a length-\(k\) path \(p\) from \(s\) to \(t\) in the \((T+1)\)-th iteration and push \(p\) to the flow in the original graph. At least one edges in \(p\) has been saturated and disappears in the BFS tree, while the opposite edges of every edge in \(p\) appears in the BFS tree.

Since this only adds edges from higher-numbered layer to lower-numbered ones, and every step on a path can advance at most by one layer, the shortest path from \(s\) to \(t\) is at least \(l\).

Furthermore, if all edges in length-\(l\) paths in the original BFS have been saturated and reversed, the shortest length becomes \(\geq l + 1\). Since each time we reverse at least one edge, this process takes at most \(|E|\) iterations.