Optimization, approximation, and complexity classes

Aitai, 1987, Recursive construction for 3-regular expanders, 295

Ausiello, 1977, On the structure of combinatorial problems and structure preserving reductions, 45

Ausiello, 1980, Structure preserving reductions among convex optimization problems, J. Comput. System Sci., 21, 136, 10.1016/0022-0000(80)90046-X

Ausiello, 1980, Toward a unified approach for the classification of NP-complete optimization problems, Theoretical Computer Science, 12, 83, 10.1016/0304-3975(80)90006-7

Berman, 1989, On the complexity of approximating the independent set problem

Cook, 1971, The complexity of Theorem Proving Procedures, 151

Fagin, 1974, Generalized first-order spectra and polynomial-time recognizable sets

Garey, 1976, The complexity of near optimal graph coloring, J. Assoc. Comput. Math., 23, 43, 10.1145/321921.321926

Garey, 1979

Johnson, 1974, Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9, 256, 10.1016/S0022-0000(74)80044-9

Karp, 1972, Reducibility among combinatorial problems, 85

P. KOLAITIS, private communication.

Krentel, 1988, The complexity of optimization problems, J. Comput. System Sci., 36, 490, 10.1016/0022-0000(88)90039-6

Kolaitis, 1987, The decision problem for the probabilities of higher-order properties, 425

Orponen, 1987, On Approximation Preserving Reductions: Complete Problems and Robust Measures

Papadimitriou, 1978, Some example of difficult traveling saleman problems, Oper. Res., 26, 434, 10.1287/opre.26.3.434

Papadimitriou, 1989

Paz, 1981, Non-deterministic polynomial optimization problems and their approximation, Theoret. Comput. Sci., 15, 251, 10.1016/0304-3975(81)90081-5

Stockmeyer, 1973, Planar 3-colorability is NP-complete, SIGACT News, 5, 19, 10.1145/1008293.1008294

Vitanyi, 1981, How well can a graph be n-colored?, Discrete Math., 10.1016/0012-365X(81)90023-6