ABSTRACT

Many combinatorial optimization problems can be cast as integer linear programming problems. A linear programming relaxation of an integer program provides a natural lower bound (in case of minimization problems) on the value of the optimal integral solution. An optimal solution to the linear programming relaxation may not necessarily be integral. If there exists a procedure to obtain an integral solution “close” to the fractional solution then we have an approximation algorithm. This process of obtaining the integral solution from the fractional one is referred to as “rounding.” Our goal is to present an ensemble of rounding techniques (which is by no means complete) that have enjoyed some success. On occasion, for detailed correctness proofs, we refer the reader to the original paper.