13.2. Randomized Rounding

in this section, we discuss the use of randomization to construct good integral solutions of ILPs from optimal solutions of their LP relaxations.

• We start with a review of randomized algorithms in Section 13.2.1, in case you have not been exposed to randomized algorithms before or you need a refresher.

• Section 13.2.2 revisits the set cover problem and discusses how to obtain an \(O(\lg n)\)-approximation of an optimal set cover via randomized rounding.

• Section 13.2.3 considers the multiway edge cut problem and discusses how to obtain a slightly better than \(2\)-approximation for this problem via randomized rounding.