$\epsilon$-Approximations with Small Packing Constraint Violation

J.-H. Lin and J. S. Vitter. ``$\epsilon$-Approximations with Small Packing Constraint Violation,'' Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC '92), Victoria, Canada, May 1992, 771-782.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

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 $\cal NP$-hard discrete optimization problem. Without any constraint violation, the $\epsilon$-approximation problem for many problems of this type is itself $\cal NP$-hard. Our methods provide polynomial-time $\epsilon$-approximations while attempting to minimize the packing constraint violation.

Our methods lead to the first known approximation algorithms with provable performance guarantees for the s-median problem, the tree pruning problem, and the generalized assignment problem. These important problems have numerous applications to data compression, vector quantization, memory-based learning, computer graphics, image processing, clustering, regression, network location, scheduling, and communication. We provide evidence via reductions that our approximation algorithms are nearly optimal in terms of the packing constraint violation. We also discuss some recent applications of our techniques to scheduling problems.