Optimization, approximation, and complexity classes

ABSTRACT

We define a natural variant of NP, MAX NP, and also a subclass called MAX SNP. These are classes of optimization problems, and in fact contain several natural, well-studied ones. We show that problems in these classes can be approximated with some bounded error. Furthermore, we show that a number of common optimization problems are complete under a kind of careful transformation (called L-reduction) that preserves approximability. It follows that such a complete problem has a polynomial-time approximation scheme iff the whole class does. These results may help explain the lack of progress on the approximability of a host of optimization problems.

REFERENCES

• A: M. Ajtai, "Recursive Construction for 3-regular Expanders", Proc. 28th Annual IEEE $;ymp. on Foundations of Computer Science, 295-304, (1987).
• ADP1: Giorgio Ausiello , Alessandro D'Atri , Marco Protasi, On the Structure of Combinatorial Problems and Structure Preserving Reductions, Proceedings of the Fourth Colloquium on Automata, Languages and Programming, p.45-60, July 18-22, 1977
• ADP2: G. Ausiello, A. D'Atri, M. Protasi, "Structure Preserving Reductions among Convex Optimization Problems", J. Comp. Sys. So. 21, 136-153, (1980).
• AMP: G. Ausiello, A. Marchetti-Spaccamela, M. Protasi, "Toward a Unified Approach for the Classification of NP- complete Optim~ation Problems", 12, 83-96, (1980).
• BS: P. Berman, G. Schnitger, "Reductions among Optimization Problems", manuscript.
• C: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• F: R. Fagin, "Generalized First-Order Spectra, and Polynomial..time Recognizable Sets", in R. Karp (ed.), Complexity of Computations, AMS, 1974.
• GJ1: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• GJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• J: D.S. Johnson, "Approximation Algorithms for Combinatorial Problems", J. Comp. Sys. Sc. 9, 256-278, (1974).
• K: P. Kotaitis, private communication.
• KV: P. Kolaitis , M. Vardi, The decision problem for the probabilities of higher-order properties, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.425-435, January 1987, New York, New York, United States [doi>10.1145/28395.28441]
• OM: P. Orponen, H. Mannila, "On Approximation Preserving Reductions: Complete Problems and Robust Measures", Technical Report, Univ. of Helsinki, (1987),
• PS: C.H. Papadimitriou and K. Steiglitz, "Some Examples of Difficult Traveling Salesman Problems", ()per. Res. 26, 434-443, (1978).
• PY: C.H. Papadimitriou, M. Yannakakis, manuscript in preparation.
• PM: A. Paz, S. Moran, "Non Deterministic Polynomial Optimization Problems and their Approximation", Theoretical Computer Science 15, 251-277, (1981).
• S: Larry Stockmeyer, Planar 3-colorability is polynomial complete, ACM SIGACT News, v.5 n.3, p.19-25, July 1973 [doi>10.1145/1008293.1008294]
• V: P. Vitanyi, "How well Can a Graph be n-colored?", Discrete Mathematics, (1981).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory