On Approximate Solutions for Combinatorial Optimization Problems

Abstract.  We demonstrate the usefulness of a special kind of approximability-preserving transformations (called continuous reductions) among combinatorial optimization problems. One common measure for the approximability of an optimization problem is its best performance ratio. This parameter attains the same value for two problems (up to a bounded factor) whenever they are mutually related by continuous reductions. Therefore, lower and upper bounds or gap-theorems valid for a particular problem are transferred along reduction chains. In this paper, continuous reductions are used for the analysis of several basic combinatorial problems including `Graph Coloring', `Consistent Deterministic Finite Automaton', `Covering by Cliques', `Covering by Complete Bipartite Subgraphs', `Independant Set', `Set Packing' and others. The results obtained and the methods involved are a contribution towards a systematic classification of NP-complete problems with regard to their approximability.