13.2.3.2.1. Randomized Rounding: Reduction to a Special Case

Lemma 13.9: For any feasible solution \(\hat x\) of (13.11) for some graph \(G\), we can construct a graph \(G'\) and a feasible solution \(\hat x'\) of (13.11) for \(G'\) such that

• \(w(\hat x') = w(\hat x)\).
• For any edge \((u,v) \in G'\), \(\hat x'_u\) and \(\hat x'_v\) differ in at most two coordinates.
• From any integral feasible solution \(\tilde x'\) of (13.11) for \(G'\), we can construct an integral feasible solution \(\tilde x\) of (13.11) for \(G\) of weight \(w(\tilde x) \le w(\tilde x')\).

This lemma provides the desired reduction of rounding an arbitrary solution \(\hat x\) to the case where \(\hat x_u\) and \(\hat x_v\) differ in at most two coordinates for every edge \((u,v) \in G\): To obtain an integral solution \(\tilde x\) of (13.11) for some graph \(G\) from an optimal solution \(\hat x\) of (13.11) for the same graph \(G\), we convert the graph \(G\) and the solution \(\hat x\) into a graph \(G'\) and a solution \(\hat x'\) as in Lemma 13.9. By the first condition of the lemma, \(w(\hat x') = w(\hat x)\). Then we round \(\hat x'\) using the rounding procedure for the special case where \(\hat x_u'\) and \(\hat x_v'\) differ in at most two coordinates for every edge \((u,v) \in G'\), to obtain an integral feasible solution \(\tilde x'\) of (13.11) for \(G'\). Finally, we use the conversion guaranteed by the third condition of the lemma to transform \(\tilde x'\) into an integral feasible solution \(\tilde x\) of (13.11) for \(G\) of weight \(w(\tilde x) \le w(\tilde x')\). If we can guarantee that \(w(\tilde x') \le \bigl(\frac{3}{2} - \frac{1}{k}\bigr) \cdot w(\hat x')\), then we obtain that

\[w(\tilde x) \le w(\tilde x') \le \left(\frac{3}{2} - \frac{1}{k}\right) \cdot w(\hat x') = \left(\frac{3}{2} - \frac{1}{k}\right) \cdot w(\hat x),\]

as desired.

Proof of Lemma 13.9: For every edge \((u,v)\) of \(G\), let \(q_{u,v}\) be the number of coordinates where \(\hat x_u\) and \(\hat x_v\) differ. Let \(q(G) = \sum_{(u,v) \in G} \max(0, q_{u,v} - 2)\). We use induction on \(q(G)\) to construct the graph \(G'\) and the solution \(\hat x'\).

If \(q(G) = 0\), then all edges in \(G\) already have the property that \(\hat x_u\) and \(\hat x_v\) differ in at most two coordinates for every edge \((u,v) \in G\). Thus, we can set \(G' = G\) and \(\hat x' = \hat x\) and the lemma holds.

If \(q(G) > 0\), then we choose an edge \((u,v)\) with \(q_{u,v} > 2\). We construct a graph \(G''\) and a feasible solution \(\hat x''\) of (13.11) for \(G''\) from \(G\) and \(\hat x\) with the following properties:

• \(w(\hat x'') = w(\hat x)\).
• \(q(G'') < q(G)\).
• From any integral feasible solution \(\tilde x''\) of (13.11) for \(G''\), we can construct an integral feasible solution \(\tilde x\) of (13.11) for \(G\) of weight \(w(\tilde x) \le w(\tilde x'')\).

By the induction hypothesis, we can then convert \(G''\) into a graph \(G'\), and \(\hat x''\) into a solution \(\hat x'\) for \(G'\) such that

• \(w(\hat x') = w(\hat x'')\).
• For any edge \((u,v) \in G'\), \(\hat x'_u\) and \(\hat x'_v\) differ in at most two coordinates.
• From any integral feasible solution \(\tilde x'\) of (13.11) for \(G'\), we can construct an integral feasible solution \(\tilde x''\) of (13.11) for \(G''\) of weight \(w(\tilde x'') \le w(\tilde x')\).

Thus, \(w(\hat x') = w(\hat x)\), and we can convert any integral feasible solution \(\tilde x'\) of (13.11) for \(G'\) into an integral feasible solution \(tilde x''\) of (13.11) for \(G''\), and \(\tilde x''\) into an integral feasible solution \(\tilde x\) of (13.11) for \(G\) such that \(w(\tilde x) \le w(\tilde x'') \le w(\tilde x')\). This proves the lemma.

Now let us discuss how to construct \(G''\) and \(\hat x''\). To obtain \(G''\) from \(G\), we replace \((u,v)\) with two edges \((u,z)\) and \((z,v)\), where \(z\) is a new vertex. We set \(w_{u,z} = w_{z,v} = w_{u,v}\). All other edges of \(G''\) are edges of \(G\) and have the same weight as in \(G\). To define the solution \(\hat x''\), we set \(\hat x''_y = \hat x_y\) for every vertex \(y \ne z\) of \(G''\). To define \(\hat x_z''\), observe that since \(\hat x_u \ne \hat x_v\), there exists an index \(i\) where \(\hat x_{u,i} \ne \hat x_{v,i}\). Assume w.l.o.g. that \(\hat x_{u,i} < \hat x_{v,i}\). Since \(\sum_{h=1}^k \hat x_{u,h} = \sum_{h=1}^k \hat x_{v,h} = 1\), this implies that there must also exist an index \(j\) where \(\hat x_{u,j} > \hat x_{v,j}\). Let \(\delta = \min(\hat x_{v,i} - \hat x_{u,i}, \hat x_{u,j} - \hat x_{v,j})\). Now we define

\[\hat x_{z,h}'' = \begin{cases} \hat x_{u,h} + \delta & \text{if } h = i\\ \hat x_{u,h} - \delta & \text{if } h = j\\ \hat x_{u,h} & \text{ if } h \notin \{i, j\}. \end{cases}\]

First note that \(\hat x''\) is a feasible solution of (13.11) for \(G''\): We have \(\hat x''_y = \hat x_y\) for all \(y \ne z\). In particular, \(\hat x''_{t_i} = \hat x_{t_i} = e_i\) for all \(1 \le i \le k\), and \(\hat x''_y = \hat x_y \in \Delta_k\) for all \(y \ne z\). For \(z\), we have \(\sum_{h=1}^k \hat x''_{z,h} = \sum_{h=1}^k \hat x_{u,h} = 1\) because \(\hat x''_z\) and \(\hat x_u\) differ only in their \(i\)th and \(j\)th coordinates, \(\hat x''_{z,i} = \hat x_{u,i} + \delta\), and \(\hat x''_{z,j} = \hat x_{u,j} - \delta\). Moreover, for \(h \notin \{i,j\}\), \(0 \le \hat x''_{z,h} \le 1\) because \(\hat x''_{z,h} = \hat x_{u,h}\) and \(0 \le \hat x_{u,h} \le 1\). For \(h \in \{i, j\}\), the choice of \(\delta\) ensures that \(0 \le \min(\hat x_{u,h}, \hat x_{v,h}) \le \hat x''_{z,h} \le \max(\hat x_{u,h}, \hat x_{v,h}) \le 1\). Thus, \(0 \le \hat x''_{z,h} \le 1\) for all \(1 \le h \le k\) and \(\sum_{h=1}^k \hat x''_{z,h} = 1\), that is, \(\hat x''_z \in \Delta_k\).

It remains to prove that \(G''\) and \(\hat x''\) satisfy the three properties above:

\(\boldsymbol{w(\hat x'') = w(\hat x)}\): Every edge \((a,b)\) with \(z \notin \{a,b\}\) has the same weight in \(G\) and \(G''\), and \(\hat x''_a = \hat x_a\) and \(\hat x''_b = \hat x_b\). Thus,

\[w(\hat x'') - w(\hat x) = w_{u,z} \cdot \bigl\|\hat x''_u - \hat x''_z\bigr\|_1 + w_{z,v} \cdot \bigl\|\hat x''_z - \hat x''_v\bigr\|_1 - w_{u,v} \cdot \bigl\|\hat x_u - \hat x_v\bigr\|_1.\]

Since \(w_{u,z} = w_{z,v} = w_{u,v}\), \(\hat x''_u = \hat x_u\), and \(\hat x''_v = \hat x_v\), this gives

\[w(\hat x'') - w(\hat x) = w_{u,v} \cdot \Bigl(\bigl\|\hat x_u - \hat x''_z\bigr|_1 + \bigl\|\hat x''_z - \hat x_v\bigr\|_1 - \bigl\|\hat x_u - \hat x_v\bigr\|_1\Bigr),\]

and \(w(\hat x'') = w(\hat x)\) if

\[\begin{multline} \bigl\|\hat x_u - \hat x''_z\bigr\|_1 + \bigl\|\hat x''_z - \hat x_v\bigr\|_1 - \bigl\|\hat x_u - \hat x_v\bigr\|_1 =\\ \sum_{h=1}^k \Bigl(\bigl|\hat x_{u,h} - \hat x''_{z,h}\bigr| + \bigl|\hat x''_{z,h} - \hat x_{v,h}\bigr| - \bigl|\hat x_{u,h} - \hat x_{v,h}\bigr|\Bigr) = 0. \end{multline}\]

For \(h \notin \{i, j\}\), we have \(\hat x''_{z,h} = \hat x_{u,h}\), so \(\bigl|\hat x_{u,h} - \hat x''_{z,h}\bigr| = 0\) and \(\bigl|\hat x''_{z,h} - \hat x_{v,h}| = |\hat x_{u,h} - \hat x_{v,h}\bigr|\). Thus,

\[\bigl|\hat x_{u,h} - \hat x''_{z,h}\bigr| + \bigl|\hat x''_{z,h} - \hat x_{v,h}\bigr| - \bigl|\hat x_{u,h} - \hat x_{v,h}\bigr| = 0.\]

For \(h \in \{i, j\}\), the choice of \(\delta\) ensures that \(\bigl|\hat x_{u,h} - \hat x''_{z,h}\bigr| = \delta\) and \(\bigl|\hat x''_{z,h} - \hat x_{v,h}\bigr| = \bigl|\hat x_{u,h} - \hat x_{v,h}\bigr| - \delta\). Thus, once again,

\[\bigl|\hat x_{u,h} - \hat x''_{z,h}\bigr| + \bigl|\hat x''_{z,h} - \hat x_{v,h}\bigr| - \bigl|\hat x_{u,h} - \hat x_{v,h}\bigr| = 0.\]

This shows that

\[\sum_{h=1}^k \Bigl(\bigl|\hat x_{u,h} - \hat x''_{z,h}\bigr| + \bigl|\hat x''_{z,h} - \hat x_{v,h}\bigr| - \bigl|\hat x_{u,h} - \hat x_{v,h}\bigr|\Bigr) = 0,\]

as required.

\(\boldsymbol{q(G'') < q(G)}\): Any edge \((a,b) \notin \{(u,v), (u,z), (z,v)\}\) is an edge of \(G\) if and only if it is an edge of \(G''\). Such an edge satisfies \(\hat x_a = \hat x_a''\) and \(\hat x_b = \hat x_b''\). Thus, this edge makes the same contribution to \(q(G)\) and \(q(G'')\) and

\[q(G'') - q(G) = \max(0,q_{u,z}-2) + \max(0,q_{z,v}-2) - \max(0,q_{u,v}-2).\]

Since \(\hat x''_u = \hat x_u\) and \(\hat x''_z\) differs from \(\hat x_u\) exactly in the coordinates \(i\) and \(j\), we have \(q_{u,z} = 2\). By the choice of \(\delta\), we have \(\hat x''_{z,i} = \hat x_{v,i} = \hat x''_{v,i}\) or \(\hat x''_{z,j} = \hat x_{v,j} = \hat x''_{v,j}\). Thus, since \(\hat x''_{z,h} = \hat x_{u,h}\) for all \(h \notin \{i, j\}\) and \(\hat x_u\) and \(\hat x_v\) differ in coordinates \(i\) and \(j\), we have \(q_{z,v} < q_{u,v}\). Since \(q_{u,v} > 2\), this implies that \(\max(0, q_{z,v} - 2) < \max(0, q_{u,v} - 2)\). Thus,

\[\max(0,q_{u,z} - 2) + \max(0, q_{z,v}-2) - \max(0, q_{u,v}-2) < 0,\]

that is, \(q(G'') < q(G)\).

Construction of an integral feasible solution \(\boldsymbol{\tilde x}\) for \(\boldsymbol{G}\) from an integral feasible solution \(\boldsymbol{\tilde x''}\) for \(\boldsymbol{G''}\): We define \(\tilde x\) as \(\tilde x_y = \tilde x''_y\) for every vertex \(y \in G\). This clearly ensures that \(\tilde x\) is an integral feasible solution of (13.11) for \(G\) if \(\tilde x''\) is an integral feasible solution of (13.11) for \(G''\). Every edge \((a,b) \in G\) with \((a,b) \ne (u,v)\) is an edge of \(G''\) and has the same weight in \(G\) and \(G''\). The edge \((u,v) \in G\) and the edges \((u,z)\) and \((z,v)\) in \(G''\) all have weight \(w_{u,v}\). Thus,

\[\begin{aligned} w(\tilde x) - w(\tilde x'') &= w_{u,v} \cdot \Bigl(\bigl\|\tilde x_u - \tilde x_v\bigr\|_1 - \bigl\|\tilde x_u'' - \tilde x_z''\bigr\|_1 - \bigl\|\tilde x_z'' - \tilde x_v''\bigr\|_1\Bigr)\\ &= w_{u,v} \cdot \Bigl(\bigl\|\tilde x_u'' - \tilde x_v''\bigr\|_1 - \bigl\|\tilde x_u'' - \tilde x_z''\bigr\|_1 - \bigl\|\tilde x_z'' - \tilde x_v''\bigr\|_1\Bigr) \end{aligned}\]

because \(\tilde x_u = \tilde x_u''\) and \(\tilde x_v = \tilde x_v''\). Since the \(L_1\)-distance is a metric—\(\|p - r\|_1 \le \|p - q\|_1 + \|q - r\|_1\) for any three vectors \(p, q, r \in \mathbb{R}^k\)—we have

\[\bigl\|\tilde x_u'' - \tilde x_v''\bigr\|_1 - \bigl\|\tilde x_u'' - \tilde x_z''\bigr\|_1 - \bigl\|\tilde x_z'' - \tilde x_v''\bigr\|_1 \le 0\]

and \(w(\tilde x) \le w(\tilde x'')\). ▨