e-approximations with minimum packing constraint violation (extended abstract)

Abstract

We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP-hard discrete optimization problem. Without any constraint violation, the ε-approximation problem for many problems of this type is itself NP-hard. Our methods provide polynomial-time ε-approximations while attempting to minimize the packing constraint violation.