Some optimal inapproximability results

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some optimal inapproximability results

Full text

Pdf (1.23 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 1 - 10

Year of Publication: 1997

ISBN:0-89791-888-6

Author

Johan Håstad

Royal Institute of Technology, Sweden

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 47, Citation Count: 75

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258533.258536 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. ARORA, C. LUND, R. MOTWAN{, M. SUDAN AND M. SZEGEDY. Proof verification and intractability of approximation problems. 33rd FOCS, 1992, pp 14-23.
	2	S. ARORA AND S. SAFRA. Probabilistic checking of proofs: a new characterization of NP. 33rd FOCS, 1992 2-13.
	3	R. B AR-YEHUDA AND S. EVEN A linear time approximation algorithm for the weighted vertex cover algorithm, Journal of Algorithms, 1991, Vol 2, pp 198-210.
	4	M. BELLARE, D. COPPERSMITH, J. HASTAD, M. KIWI, AND M. SUDAN, Linearity testing in characteristic two, IEEE Transactions on Information, Vol 42, No 6, November 1996, pp 1781-1796.
	5	M. Bellare , O. Goldreich , M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.422, October 23-25, 1995
	6	M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
	7	Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
	8	Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.182, January 04-06, 1995
	9	Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
	10	M.R. GARF. Y AND D.S. JOHNSSON, Computers and Intractability, W.H. Freeman and Company, 1979.
	11	Michel X. Goemans , David P. Williamson, .879-approximation algorithms for MAX CUT and MAX 2SAT, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.422-431, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195216]
	12	J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
	13	D.S. JOHNSSON Approximation algorithms for combinatorial problems, J. Computer and System Sciences, 1974, Vol 9, pp 256-278.
	14	C. PAPADIMITRIOU AND M. YANNAKAKIS Optimization, approximation and complexity classes. Journal of Computer and System Sciences, Vol 43, 1991, pp 425- 440.
	15	E. PETRANK The hardness of approximation, 2nd ISTCS, 1993, pp 275-284.
	16	Ran Raz, A parallel repetition theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.447-456, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225181]
	17	L. Trevisan , G. B. Sorkin , M. Sudan , D. P. Williamson, Gadgets Approximation, and Linear Programming, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.617, October 14-16, 1996
	18	Oleg Verbitsky, Towards the parallel repetition conjecture, Theoretical Computer Science, v.157 n.2, p.277-282, May 5, 1996 [doi>10.1016/0304-3975(95)00165-4]

CITED BY 75

	Uri Zwick, Finding almost-satisfying assignments, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.551-560, May 24-26, 1998, Dallas, Texas, United States
	Uriel Feige , Gideon Schechtman, On the integrality ratio of semidefinite relaxations of MAX CUT, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.433-442, July 2001, Hersonissos, Greece
	Shai Halevi , Robert Krauthgamer , Eyal Kushilevitz , Kobbi Nissim, Private approximation of NP-hard functions, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.550-559, July 2001, Hersonissos, Greece
	Uri Zwick, Computer assisted proof of optimal approximability results, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.496-505, January 06-08, 2002, San Francisco, California
	Gunnar Andersson , Lars Engebretsen , Johan Håstad, A new way to use semidefinite programming with applications to linear equations mod p, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.41-50, January 17-19, 1999, Baltimore, Maryland, United States
	Eran Halperin , Dror Livnat , Uri Zwick, MAX CUT in cubic graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.506-513, January 06-08, 2002, San Francisco, California
	Zoë Abrams , Ashish Goel , Serge Plotkin, Set k-cover algorithms for energy efficient monitoring in wireless sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
	Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998
	Noga Alon , Benny Sudakov , Uri Zwick, Constructing worst case instances for semidefinite programming based approximation algorithms, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.92-100, January 07-09, 2001, Washington, D.C., United States
	Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece
	Eran Halperin , Uri Zwick, Combinatorial approximation algorithms for the maximum directed cut problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.1-7, January 07-09, 2001, Washington, D.C., United States
	Thomas Erlebach , Klaus Jansen , Eike Seidel, Polynomial-time approximation schemes for geometric graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.671-679, January 07-09, 2001, Washington, D.C., United States
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States
	Luca Trevisan, When Hamming meets Euclid: the approximability of geometric TSP and MST (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.21-29, May 04-06, 1997, El Paso, Texas, United States
	Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998
	Christos H. Papadimitriou , Santosh Vempala, On the approximability of the traveling salesman problem (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.126-133, May 21-23, 2000, Portland, Oregon, United States
	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998
	Takao Asano , David P. Williamson, Improved approximation algorithms for MAX SAT, Journal of Algorithms, v.42 n.1, p.173-202, January 2002
	John M. Hitchcock, MAX3SAT is exponentially hard to approximate if NP has positive dimension, Theoretical Computer Science, v.289 n.1, p.861-869, 23 October 2002
	Oded Goldreich , Shafi Goldwasser, On the limits of non-approximability of lattice problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.1-9, May 24-26, 1998, Dallas, Texas, United States
	Alberto Caprara , Giuseppe F. Italiano , G. Mohan , Alessandro Panconesi , Aravind Srinivasan, Wavelength rerouting in optical networks, or the Venetian Routing problem, Journal of Algorithms, v.45 n.2, p.93-125, November 2002
	Uri Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.679-687, May 01-04, 1999, Atlanta, Georgia, United States
	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998
	Eran Halperin, Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.329-337, January 09-11, 2000, San Francisco, California, United States
	Takao Asano , David P. Williamson, Improved approximation algorithms for MAX SAT, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.96-105, January 09-11, 2000, San Francisco, California, United States
	Edward A. Hirsch, Worst-case study of local search for MAX-k-SAT, Discrete Applied Mathematics, v.130 n.2, p.173-184, 15 August 2003
	Gerald Gruber , Franz Rendl, The bundle method for hard combinatorial optimization problems, Combinatorial optimization - eureka, you shrink!, Springer-Verlag New York, Inc., New York, NY, 2003
	Cristina Bazgan , W. Fernandez de la Vega , Marek Karpinski, Polynomial time approximation schemes for dense instances of minimum constraint satisfaction, Random Structures & Algorithms, v.23 n.1, p.73-91, August 2003
	Endre Boros , Peter L. Hammer, Pseudo-boolean optimization, Discrete Applied Mathematics, v.123 n.1-3, p.155-225, 15 November 2002
	Marcos Kiwi , Frédéric Magniez , Miklos Santha, Exact and approximate testing/correcting of algebraic functions: a survey, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
	Rudi Pendavingh , Petra Schuurman , Gerhard J. Woeginger, Recognizing DNA graphs is difficult, Discrete Applied Mathematics, v.127 n.1, p.85-94, April 2003
	Shai Ben-David , Nadav Eiron , Philip M. Long, On the difficulty of approximately maximizing agreements, Journal of Computer and System Sciences, v.66 n.3, p.496-514, May 2003
	Noga Alon , Asaf Shapira, Testing satisfiability, Journal of Algorithms, v.47 n.2, p.87-103, July 2003
	Martin Thimm, On the approximability of the Steiner tree problem, Theoretical Computer Science, v.295 n.1-3, p.387-402, 24 February 2003
	Noga Alon , Asaf Shapira, Testing satisfiability, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.645-654, January 06-08, 2002, San Francisco, California
	Luca Trevisan, Recycling queries in PCPs and in linearity tests (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.299-308, May 24-26, 1998, Dallas, Texas, United States
	Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States
	Jianer Chen , Iyad A. Kanj, On approximating minimum vertex cover for graphs with perfect matching, Theoretical Computer Science, v.337 n.1-3, p.305-318, 9 June 2005
	Don Coppersmith , David Gamarnik , Mohammad Hajiaghayi , Gregory B. Sorkin, Random MAX SAT, random MAX CUT, and their phase transitions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Surajit Chaudhuri , Mayur Datar , Vivek Narasayya, Index Selection for Databases: A Hardness Study and a Principled Heuristic Solution, IEEE Transactions on Knowledge and Data Engineering, v.16 n.11, p.1313-1323, November 2004
	Daniel Král, Locally satisfiable formulas, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Jonas Holmerin , Subhash Khot, A new PCP outer verifier with applications to homogeneous linear equations and max-bisection, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Nader H. Bshouty , Lynn Burroughs, Maximizing Agreements with One-Sided Error with Applications to Heuristic Learning, Machine Learning, v.59 n.1-2, p.99-123, May 2005
	Detlef Sieling, The nonapproximability of OBDD minimization, Information and Computation, v.172 n.2, p.103-138, January 29, 2002
	Subhash Khot, Hardness results for approximate hypergraph coloring, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Marco E. Lübbecke , Uwe T. Zimmermann, Shunting Minimal Rail Car Allocation, Computational Optimization and Applications, v.31 n.3, p.295-308, July 2005
	Shahar Dobzinski , Noam Nisan , Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Reuven Bar-Yehuda , Keren Bendel , Ari Freund , Dror Rawitz, Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004, ACM Computing Surveys (CSUR), v.36 n.4, p.422-463, December 2004
	Mikhail Alekhnovich , Sanjeev Arora , Iannis Tourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Erik D. Demaine , Mohammad Taghi Hajiaghayi , Uriel Feige , Mohammad R. Salavatipour, Combination can be hard: approximability of the unique coverage problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.162-171, January 22-26, 2006, Miami, Florida
	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	B. Bollobás , A. D. Scott, Problems and results on judicious partitions, Random Structures & Algorithms, v.21 n.3-4, p.414-430, October 2002
	Mayur Datar , Tomás Feder , Aristides Gionis , Rajeev Motwani , Rina Panigrahy, A combinatorial algorithm for MAX CSP, Information Processing Letters, v.85 n.6, p.307-315, 31 March 2003
	J. A. De Loera , R. Hemmecke , M. Köppe , R. Weismantel, FPTAS for mixed-integer polynomial optimization with a fixed number of variables, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.743-748, January 22-26, 2006, Miami, Florida
	Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Zdeněk Dvořák , Daniel Král , Ondřej Pangrác, Locally consistent constraint satisfaction problems, Theoretical Computer Science, v.348 n.2, p.187-206, 8 December 2005
	Takao Asano, An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT, Theoretical Computer Science, v.354 n.3, p.339-353, 4 April 2006
	Uri Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.201-210, January 25-27, 1998, San Francisco, California, United States
	Nader H. Bshouty , Lynn Burroughs, Maximizing agreements and coagnostic learning, Theoretical Computer Science, v.350 n.1, p.24-39, 18 January 2006
	Irit Dinur , Shmuel Safra, The importance of being biased, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Uriel Feige , Gideon Schechtman, On the optimality of the random hyperplane rounding technique for max cut, Random Structures & Algorithms, v.20 n.3, p.403-440, May 2002
	Craig A. Tovey, Tutorial on computational complexity, Interfaces, v.32 n.3, p.30-61, May-June 2002
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Murtuza Jadliwala , Qi Duan , Jinhui Xu , Shambhu Upadhyaya, On extracting consistent graphs in wireless sensor networks, International Journal of Sensor Networks, v.2 n.3/4, p.149-162, April 2007
	James Aspnes , Kevin Chang , Aleksandr Yampolskiy, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, Journal of Computer and System Sciences, v.72 n.6, p.1077-1093, September 2006
	Alberto Bertoni , Paola Campadelli , Marco Carpentieri , Giuliano Grossi, A Genetic Model: Analysis and Application to MAXSAT, Evolutionary Computation, v.8 n.3, p.291-309, September 2000
	Dekel Tsur, Tree-edges deletion problems with bounded diameter obstruction sets, Discrete Applied Mathematics, v.155 n.10, p.1275-1293, May, 2007
	B. Bollobás , A. D. Scott, Max Cut for Random Graphs with a Planted Partition, Combinatorics, Probability and Computing, v.13 n.4-5, p.451-474, July 2004
	Noga Alon , Benny Sudakov, Bipartite Subgraphs and the Smallest Eigenvalue, Combinatorics, Probability and Computing, v.9 n.1, p.1-12, January 2000
	Orestes Bueno , Prabhu Manyem, Polynomial-TimeMaximisation Classes: Syntactic Hierarchy, Fundamenta Informaticae, v.84 n.1, p.111-133, August 2008
	Ryan O'Donnell , Yi Wu, 3-bit dictator testing: 1 vs. 5/8, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.365-373, January 04-06, 2009, New York, New York
	Mary Ashley , Tanya Berger-Wolf , Piotr Berman , Wanpracha Chaovalitwongse , Bhaskar DasGupta , Ming-Yang Kao, On approximating four covering and packing problems, Journal of Computer and System Sciences, v.75 n.5, p.287-302, August, 2009
	Guohua Jin , Luay Nakhleh , Sagi Snir , Tamir Tuller, Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.6 n.3, p.495-505, July 2009