13.2.3.2. A Monte Carlo Algorithm

Our algorithm for the multiway edge cut problem now constructs the LP relaxation of (13.8) and finds an optimal solution \(\bigl(\hat x, \hat d\bigr)\) for it in polynomial time. \(\hat x\) is an optimal solution of (13.11). To obtain a multiway edge cut \(C\), we round \(\hat x\) to obtain an integral feasible solution \(\tilde x\) of (13.11). This solution satisfies \(\tilde x_v \in \{e_1, \ldots, e_k\}\) for every vertex in \(V\), not only for the terminals, because \(e_1, \ldots, e_k\) are the only vectors in \(\Delta_k\) with integral coordinates. Thus, \(\tilde x\) defines a partition of the vertex set of \(G\) into subsets \(V_1, \ldots, V_k\) where

\[V_i = \{ v \in V \mid \tilde x_v = e_i \} \quad \forall 1 \le i \le k.\]

Since \(\tilde x_{t_i} = e_i\) for all \(1 \le i \le k\), \(t_i\) is the only terminal in \(V_i\) and the set

\[C = \{ (u,v) \in E \mid \tilde x_u \ne \tilde x_v \}\]

is a valid multiway edge cut of weight \(w(\tilde x)\).

The rounding process that constructs \(\tilde x\) from \(\hat x\) ensures that \(w(\tilde x) \le \bigl(\frac{3}{2} - \frac{1}{k}\bigr) \cdot w(\hat x)\). Since \(\hat x\) is an optimal fractional solution of (13.11) and any optimal multiway edge cut corresponds to an integral feasible solution of (13.11), we have \(w(\hat x) = \textrm{OPT}_f \le \textrm{OPT}\). Thus, \(w(\tilde x) \le \bigl(\frac{3}{2} - \frac{1}{k}\bigr) \cdot \textrm{OPT}\) and \(C\) is a \(\bigl(\frac{3}{2} - \frac{1}{k}\bigr)\)-approximation of an optimal multiway edge cut.

We describe the construction of \(\tilde x\) from \(\hat x\) in two phases:

• First we discuss how to reduce rounding an arbitrary solution \(\hat x\) to the special where \(\hat x_u\) and \(\hat x_v\) differ in at most two coordinates, for every edge \((u,v) \in G\).

• Then we discuss how to round a solution that satisfies this condition.