13.2.3.3. A Las Vegas Algorithm

So far, we have obtained a polynomial-time Monte Carlo approximation algorithm for the multiway edge cut problem: We solve the LP relaxation of (13.8), round it to obtain an integral solution \(\tilde x\) of (13.11) using the procedure above. This integral solution \(\tilde x\) corresponds to a multiway edge cut \(C\). By Corollary 13.11, the expected weight of this multiway edge cut is at most \(\bigl(\frac{3}{2} - \frac{1}{k}\bigr) \cdot \textrm{OPT}_f\). Next we convert this algorithm into a Las Vegas approximation algorithm for the multiway edge cut problem: Its approximation ratio is guaranteed to be at most \(\frac{3}{2}\), and its expected running time is polynomial in the input size. Note that the Las Vegas algorithm achieves only an approximation ratio of \(\frac{3}{2}\), not \(\frac{3}{2} - \frac{1}{k}\). The fact that the Monte Carlo algorithm achieves this better approximation ratio is crucial for constructing the Las Vegas algorithm.

Lemma 13.12: There exists a Las Vegas randomized \(\frac{3}{2}\)-approximation algorithm for the multiway edge cut problem.

Proof: By Corollary 13.11, running the Monte Carlo algorithm once produces a multiway edge cut \(C\) of expected weight at most \(\bigl(\frac{3}{2} - \frac{1}{k}\bigr) \cdot \textrm{OPT}_f\). Since we can compute \(w(C)\) and \(\textrm{OPT}_f\) in polynomial time, we can test whether \(w(C) \le \frac{3}{2} \cdot \textrm{OPT}_f\). If so, we report \(C\) as the desired multiway edge cut. Otherwise, we rerun the algorithm until we obtain a multiway edge cut of weight at most \(\frac{3}{2} \cdot \textrm{OPT}_f\).

By Markov's inequality, the probability that the weight of the multiway edge cut computed by the Monte Carlo algorithm exceeds \(\frac{3}{2} \cdot \textrm{OPT}_f\) is at most

\[\frac{3/2 - 1/k}{3/2} = 1 - \frac{2}{3k}.\]

The expected number of repetitions of the Monte Carlo algorithm before finding a cut of weight at most \(\frac{3}{2} \cdot \textrm{OPT}_f\) is thus at most

\[\sum_{i=1}^\infty \left( 1 - \frac{2}{3k}\right)^{i-1} = \frac{3k - 2}{2}.\]

Since \(k \le n\), this is bounded by \(\frac{3n - 2}{2} = O(n)\). Thus, the expected running time of the algorithm is \(O(n)\) times the cost of a single invocation of the Monte Carlo algorithm. Since the Monte Carlo algorithm runs in polynomial time, the expected running time of the Las Vegas algorithm is also polynomial. ▨