Randomized rounding on Linear Programming

“Within computer science and operations research, many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). Many such problems do admit fast (polynomial time) approximation algorithms – that is, algorithms that are guaranteed to return an approximately optimal solution given any input.

Randomized rounding (Raghavan & Tompson 1987) is a widely used approach for designing and analyzing such approximation algorithms. The basic idea is to use the probabilistic method to convert an optimal solution of a relaxation of the problem into an approximately optimal solution to the original problem.” – from Wikipedia

In the following we prove the correctness of randomized rounding on LP, given the optimal value.

Continue reading

Approximation algorithm for multiway-cut

Given a graph $G(V,E)$ and a set $T\subset V$ of $k$ terminal vertices, a multiway-cut is a set $C\subset E$ of edges such that in $G'(V,E-C)$, no path exists between any two nodes of $T$. The multiway-cut problem is defined as finding the multiway-cut where $\vert C\vert$ is minimal. Multi-way cut terminal problem is known to be NP-hard for $k \geq 3$.

Again, using approximation we can make a faster algorithm.

Continue reading

Approximation algorithm for partial set cover

The set cover problem (SCP)  is a classical question in combinatorics, computer science and complexity theory.

Briefly, a set of elements and a set of sets that contains different elements are given. Each set has an associated cost. The goal is cover every elements paying the less cost possible.

The partial set cover is a slightly different problem, in which is required to cover at least a given percentage of items paying the less cost possible. The problem is known to be NP-complete, but using approximation good results can be achieved with ease. In the following we analyze the correctness of a greedy approximation algorithm for partial set cover.

Continue reading