The hardness of approximation: Gap location

M. Ajtai, Recursive Construction for 3-Regular Expanders. InProc. 28th Ann. Symp. Found. Comput. Sci., 1987, 295?304.

N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, The Algorithmic Aspects of the Regularity Lemma. InProc. 33th Ann. Symp. Found. Comput. Sci., 1992, 473?482.

S. Arora and S. Safra, Probabilistic Checking of Proofs: A New Characterization of NP. InProc. 33th Ann. Symp. Found. Comput. Sci., 1992, 1?13.

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof Verification and Intractability of Approximation Problems. InProc. 33th Ann. Symp. Found. Comput. Sci., 1992, 14?23.

M. Bellare and E. Petrank, private communication, 1992.

C. Berge,Graph and Hypergraphs. North-Holland, Amsterdam, 1973.

M. Bern andP. Plassmann, The Steiner problem with edge lengths 1 and 2.Inform. Process. Lett. 32 (1989), 171?176.

A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yannakakis, Linear Approximation of Shortest Superstrings. InProc. 31th Ann. Symp. Found. Comput. Sci., 1990, 554?562.

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The Complexity of Multiway Cuts. InProc. Twenty-forth Ann. ACM Symp. Theor. Comput., 1992, 241?251.

U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy, Approximating clique is almost NP-complete. InProc. 32th Ann. Symp. Found. Comput. Sci., 1991, 2?12.

O. Gabber andZ. Galil, Explicit Construction of linear sized superconcentrators.J. Comput. System Sci. 22 (1981), 407?420.

M. R. Garey andD. S. Johnson, The complexity of near-optimal graph coloring.J. Assoc. Comput. Mach. 23 (1976), 43?49.

M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

M. R. Garey, D. S. Johnson, andL. J. Stockmeyer, Some Simplified NP-Complete Graph Problems.Theoret. Comput. Sci. 1 (1976), 237?267.

J. Hastad, S. Phillips, and S. Safra, A well Characterized Approximation Problem. InProceedings of the 2nd Israel Symposium on Theory of Computing and Systems, 1993, 261?265.

I. Hoyler, The NP-Competeness of Edge Coloring.SIAM J. Comput. 10 (1981), 718?720.

V. Kann Maximum Bounded 3-Dimensional Matching is MAX SNP-Complete.Inform. Process. Lett. 37 (1991), 27?35.

R. M. Karp, Reducibility among combinatorial problems. InComplexity of Computer Computations, ed.Raymond E. Miller and James W. Thatcher, Plenum Press, 1972, 85?103.

D. Leven andZ. Galil, NP-completness of finding the chromatic index of regular graphs.J. Algorithms 4 (1983), 35?44.

L. Lovász, Coverings and Colorings of Hypergraphs. InProc. 4-th Southern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, 1973, 3?12.

C. Lund and M. Yannakakis, On the Hardness of Approximating Minimization Problems. InProc. Twenty-fifth Ann. ACM Symp. Theor. Comput., 1993, 286?293.

G. A. Margulis, Explicit Constructions of Concentrators.Comm. ACM 9 (1973), 71?80. (English translation inProblems Inform. Transmission, 1975, 325?332.).

R. Motwani, Lecture Notes on Approximation Algorithms. Technical report, Dept. of Computer Science, Stanford University, 1992.

C. H. Papadimitriou andM. Yannakakis, Optimization, Approximation, and Complexity Classes.J. Comput. System Sci. 43 (1991), 425?440.

C. H. Papadimitriou and M. Yannakakis, The Traveling Salesman Problem with Distances One and Two.Mathematics of Operations Research (to appear).

E. Petrank, The Hardness of Approximation: Gap Location. InProceedings of the 2nd Israel Symposium on Theory of Computing and Systems, 1993, 275?284.

S. Sahni andT. Gonzalez, P-complete approximation problems.J. Assoc. Comput. Mach. 23 (1976), 555?565.

L. J. Stockmeyer, Planar 3-Colorability is NP-Complete.SIGACT News 5(3) (1973), 19?25.