On the hardness of approximating minimization problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the hardness of approximating minimization problems

Full text

Pdf (805 KB)

Source

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

San Diego, California, United States

Pages: 286 - 293

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Carsten Lund
Mihalis Yannakakis

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 20, Citation Count: 43

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/167088.167172 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	N. Alon, O. Goldreich, J. H~stad, and R. Peralta. Simple constructions of almost k-wise independent random variables. In Proc. of the 31st IEEE Syrup. on Foundations of Computer Science, pages 544- 553, 1990.
	2	S. Arora, C. Lund, t#. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proc. of the 33rd IEEE Syrup. on Foundations of Computer Science, 1992.
	3	S. Arora and S. Safra. Approximating clique is NP- complete. In Proc. of the 33rd IEEE Syrup. on Foundations of Computer Science, 1992.
	4	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]
	5	M. Beilare. Interactive proofs and Approximation. IBM Research Report RC 17831, 1992.
	6	A. Blum. Some tools for approximate 3-coloring. In Proc. of the 31st IEEE Syrup. on Foundations of Computer Science, pages 554-562, 1990.
	7	P. Berman , G. Schnitger, On the complexity of approximating the independent set problem, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science on STACS 89, p.256-268, February 1989, Paderborn, Germany
	8	V. Chvatal. A greedy heuristic for the set covering problem. Mathematics of Operations Research, 4:233-235, 1979.
	9	Anne Condon, The complexity of the max word problem and the power of one-way interactive proof systems, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.456-465, February 1991, Hamburg, Germany
	10	G. Dobson. Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Mathematics of Operations Research, 7:515-531, 1982.
	11	U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
	12	Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
	13	M. L. Fisher and L. A. Wolsey. On the greedy heuristic for continuous covering and packing problems. SIAM J. Algebraic Discrete Methods, 3:584- 591, 1982.
	14	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]
	15	M. Grotschei, L. Ldvasz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169-197, 1981.
	16	M. M. Hallddrsson. A still better performance guarantee for approximate graph coloring. Technical Report 90-44, DIMACS, 1990.
	17	D. S. Johnson. Approximation algorithms for combinatorial problems. J. of Computer and System Sciences, 9:256-278, 1974.
	18	D. S. Johnson. Worst case behavior of graph coloring algorithms. In Proc. 5th Southeastern Conf. on Combznatorics, Graph Theory and Computing, pages 513-527. Utilitas Mathematica Publ., Winnipeg, Ontario, 1974.
	19	R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, Advances in Computing Research, pages 85-103. Plenum Press, 1972.
	20	P. G. Kolaitis and M. N. Thakur. Approximation properties of NP minimization classes. In Proc. of the 6th Conference on Structure in Complexity Theory, pages 353-366, 1991.
	21	L. Lovasz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975.
	22	Dror Lapidot , Adi Shamir, Fully parallelized multi prover protocols for NEXP-time (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.13-18, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185342]
	23	N. Linial and U. Vazirani. Graph products and chromatic numbers. In Proc. of the 30th IEEE Symp. on Foundations of Compuler Science, pages 124-133, 1989.
	24	J. Orlin. Contentment in graph theory: covering graphs with cliques. In Proc. Konik. Neder. Akad. Wet., volume 80, pages 406-424, 1977.
	25	A. Paz and S. Moran. Non deterministic polynomial optimization problems and their approximations. Theoretical Computer Science, 15:251-277, 1981.
	26	Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
	27	H. U. Simon. On approximate solutions for combinatorial optimization problems. SIAM J. Algebraic Discrete Methods, 3:294-310, 1990.
	28	Avi Wigderson, Improving the performance guarantee for approximate graph coloring, Journal of the ACM (JACM), v.30 n.4, p.729-735, Oct. 1983 [doi>10.1145/2157.2158]
	29	L. A. Wolsey. An analysis of the greedy algorithm for the submodulat set covering problem. Combinatomca, 2:385-393, 1982.
	30	L. T. Kou , L. J. Stockmeyer , C. K. Wong, Covering edges by cliques with regard to keyword conflicts and intersection graphs, Communications of the ACM, v.21 n.2, p.135-139, Feb. 1978 [doi>10.1145/359340.359346]

CITED BY 43

	John Kececioglu , Dan Gusfield, Reconstructing a history of recombinations from a set of sequences, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.471-480, January 23-25, 1994, Arlington, Virginia, United States
	C.-J. Shi , J. A. Brzozowski, Cluster-cover: a theoretical framework for a class of VLSI-CAD optimization problems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.1, p.76-107, Jan. 1998
	Hervé Brönnimann , Michael T. Goodrich, Almost optimal set covers in finite VC-dimension: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.293-302, June 06-08, 1994, Stony Brook, New York, United States
	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, ACM SIGMOD Record, v.27 n.2, p.94-105, June 1998
	Andrea E. F. Clementi , Miriam Di Ianni, On the hardness of approximating optimum schedule problems in store and forward networks, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.272-280, April 1996
	Rudolf Mathar , Thomas Niessen, Optimum positioning of base stations for cellular radio networks, Wireless Networks, v.6 n.6, p.421-428, Dec. 2000
	L. J. Cowen , W. Goddard , C. E. Jesurum, Coloring with defect, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 05-07, 1997, New Orleans, Louisiana, United States
	Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States
	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States
	R. Ravi , M. V. Marathe , S. S. Ravi , D. J. Rosenkrantz , H. B. Hunt, III, Many birds with one stone: multi-objective approximation algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.438-447, May 16-18, 1993, San Diego, California, United States
	Sundar Vishwanathan, An O(log*n) approximation algorithm for the asymmetric p-center problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.1-5, January 28-30, 1996, Atlanta, Georgia, United States
	Uriel Feige , Joe Kilian, Impossibility results for recycling random bits in two-prover proof systems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.457-468, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Ehud Aharoni , Reuven Cohen, Restricted dynamic Steiner trees for scalable multicast in datagram networks, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.286-297, June 1998
	David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998
	Uri Feige , Joe Kilian, Two prover protocols: low error at affordable rates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.172-183, May 23-25, 1994, Montreal, Quebec, Canada
	Dimitris Bertsimas , Chung-Piaw Teo, From valid inequalities to heuristics: a unified view of primal-dual approximation algorithms in covering problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.102-111, January 22-24, 1995, San Francisco, California, United States
	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
	Sandy Irani , Vitus Leung, Scheduling with conflicts, and applications to traffic signal control, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.85-94, January 28-30, 1996, Atlanta, Georgia, United States
	Yair Bartal , Amos Fiat , Stefano Leonardi, Lower bounds for on-line graph problems with application to on-line circuit and optical routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.531-540, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	S. Ramanathan, Multicast tree generation in networks with asymmetric links, IEEE/ACM Transactions on Networking (TON), v.4 n.4, p.558-568, Aug. 1996
	Uriel Feige, Randomized graph products, chromatic numbers, and Lovasz j-function, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.635-640, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Amotz Bar-Noy , Alain Mayer , Baruch Schieber , Madhu Sudan, Guaranteeing fair service to persistent dependent tasks, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.243-252, January 22-24, 1995, San Francisco, California, United States
	Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994
	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
	Sandy Irani , Vitus Leung, Probabilistic analysis for scheduling with conflicts, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.286-295, January 05-07, 1997, New Orleans, Louisiana, United States
	M. Bellare , S. Goldwasser , C. Lund , A. Russell, Efficient probabilistic checkable proofs and applications to approximation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.820, May 23-25, 1994, Montreal, Quebec, Canada
	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada
	V. S. Anil Kumar , H. Ramesh, Covering rectilinear polygons with axis-parallel rectangles, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.445-454, May 01-04, 1999, Atlanta, Georgia, United States
	Guy Kortsarz , David Peleg, Approximating shallow-light trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.103-110, January 05-07, 1997, New Orleans, Louisiana, United States
	Oh-Heum Kwon , Kyung-Yong Chwa, Approximation algorithms for general parallel task scheduling, Information Processing Letters, v.81 n.3, p.143-150, 14 February 2002
	Marc Demange, A Note on the Approximation of a Minimum-Weight Maximal Independent Set, Computational Optimization and Applications, v.14 n.1, p.157-169, July 1999
	David Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoretical Computer Science, v.282 n.2, p.231-257, 10 June 2002
	Tei-Wei Kuo , Aloysius K. Mok, Incremental Reconfiguration and Load Adjustment in Adaptive Real-Time Systems, IEEE Transactions on Computers, v.46 n.12, p.1313-1324, December 1997
	Eran Halperin , Richard M. Karp, The minimum-entropy set cover problem, Theoretical Computer Science, v.348 n.2, p.240-250, 8 December 2005
	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
	Anup Rao, Parallel repetition in projection games and a concentration bound, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Magnús M. Halldórsson, Approximating discrete collections via local improvements, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.160-169, January 22-24, 1995, San Francisco, California, United States
	Igal Galperin, Analysis of greedy expert hiring and an application to memory-based learning (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.217-223, June 28-July 01, 1996, Desenzano del Garda, Italy
	Massimiliano Caramia , Paolo Dell'Olmo, Coloring graphs by iterated local search traversing feasible and infeasible solutions, Discrete Applied Mathematics, v.156 n.2, p.201-217, January, 2008
	Andreas Birkendorf , Hans Ulrich Simon, Using computational learning strategies as a tool for combinatorial optimization, Annals of Mathematics and Artificial Intelligence, v.22 n.3-4, p.237-257, 1998
	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic Subspace Clustering of High Dimensional Data, Data Mining and Knowledge Discovery, v.11 n.1, p.5-33, July 2005
	Oded Goldreich, A taxonomy of proof systems (part 2), ACM SIGACT News, v.25 n.1, p.22-30, March 1994
	Russell Greiner, The complexity of theory revision, Proceedings of the 14th international joint conference on Artificial intelligence, p.1162-1168, August 20-25, 1995, Montreal, Quebec, Canada