Simon, Hans Ulrich On approximate solutions for combinatorial optimization problems. (English) Zbl 0699.68077 SIAM J. Discrete Math. 3, No. 2, 294-310 (1990). Summary: The usefulness of a special kind of approximability-preserving transformations (called continuous reductions) among combinatorial optimization problems is demonstrated. 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. 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, independent 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. Cited in 31 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 03D15 Complexity of computation (including implicit computational complexity) Keywords:reductions; NP-completeness; approximation algorithms; consistent; automata; partitioning; combinatorial optimization; graph coloring; covering; independent set; set packing × Cite Format Result Cite Review PDF Full Text: DOI