|
Abstract : |
\Lambda Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy under contract DE-AC04- 94AL85000. ySupported by NSF CAREER award CCR-9875024. 1 1 Introduction Randomized rounding has become a standard technique in the design of approximation algorithms for NP-hard optimization problems, especially for packing and covering problems. These are problems that can be stated as integer linear programs (IP's) of the form max cx subject to Ax ^ b or min cx subject to Ax * b where each component of x is 0-1 valued and the entries of A; b and c are all non-negative. Given say, a minimization (covering) problem of this form, the approach is to first solve the linear programming relaxation of the integer program, namely min cx, |
