Polynomial time approximation schemes for dense instances of NP-hard problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polynomial time approximation schemes for dense instances of NP-hard problems

Full text

Pdf (909 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 284 - 293

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Sanjeev Arora	Princeton University
David Karger	MIT Laboratory for Computer Science, AT&T Bell Laboratories
Marek Karpinski	University of Bonn

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): 46, Citation Count: 38

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/225058.225140 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.

	AFW94	N. Alon, A. Frieze, and D. Welsh. Poly-nomial time randomized approximation schemes for the tutte polynomial of dense graphs. In Proc. 35 'h FOCS, pages 24- 35. IEEE, IEEE Computer Society Press, November 1994.
	ALM+92	S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd FOG'S, pages 14-23. IEEE, October 1992.
	AS92	S. Arora and S. Safra. Probabilistic check-ing of proofs: A new characterization of NP. In Proc. 33rd FOG'S, pages 2-13, IEEE, 1992.
	BCLS84	T. Bui, S. Chaudhuri, T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. In Proc. 25th FOCS, pages 181-192. IEEE, 1984.
	BGG93	Mihir Bellare , Oded Goldreich , Shafi Goldwasser, Randomness in interactive proofs, Computational Complexity, v.3 n.4, p.319-354, Oct. 1993 [doi>10.1007/BF01275487]
	BH92	Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
	BR94	M. Bellare and J. Rompel. Randomness-efficient oblivious sampling. In Proc. 35th FOCS, pages 276-287. IEEE, 1994.
	DJP+92	E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The complexity of multiway cuts (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.241-251, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129736]
	dlV94	W.F. de la Vega. MAXCUT has a ran-domized approximation scheme in dense graphs. manuscript, October 1994.
	Edw86	K Edwards, The complexity of colouring problems on dense graphs, Theoretical Computer Science, v.43 n.2-3, p.337-343, July 1986
	FG95	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
	FGL+91	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]
	Gi193	D. Gillman. A chernoff bound for random walks on expanders. In Proc. 34th FOCS, pages 680-691. IEEE, November 1993.
	GW94	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]
	IK75	Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
	JS89	M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
	JS93	M. Jerrum and G. B. Sorkin. Simulated annealing for graph bisection. In Proc. 34th FOCS, pages 94-103. IEEE, Novem-ber 1993.
	KK82	N. Karmaker and R.M. Karp. An effi-cient approximation scheme for the one-dimensional bin-packing problem. In Proc. 23r~ FOCS, pages 312-320. IEEE, 1982.
	KP93	G. Kortsarz and D. Peleg. On choosing a dense subgraph. In Proc. 34th FOCS, pages 692-701. IEEE, November 1993.
	KPa92	Elias Koutsoupias , Christos H. Papadimitriou, On the greedy algorithm for satisfiability, Information Processing Letters, v.43 n.1, p.53-55, Aug. 10, 1992 [doi>10.1016/0020-0190(92)90029-U]
	LR88	T. Leighton and S. Rae. An approxi-mate max-flow rein-cut theorem for uni-form multicommodity flow problems with applications to approximation algorithms. In Proc. 29th FOG'S, pages 422-431. IEEE, October 1988.
	LY93	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
	Pap94	C. H. Papadimitriou. Compuiattonal Complexity. Addison-Wesley, 1994.
	PY91	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]
	P076	L. P6sa. Hamiltonian circuits in random graphs. Dzscreie Mathemat~cs, 14:359-364, 1976.
	R88	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	RT87	Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
	Shm94	D. Shmoys. Computing near-optimal solu-tions to combinatorial optimization prob-lems. To appear in Dimacs Series m Dw-crete Math and Theoretical Computer Sct-ence, 1994.
	Yan92	Mihalis Yannakakis, On the approximation of maximum satisfiability, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.1-9, September 1992, Orlando, Florida, United States

CITED BY 39

	Ravindran Kannan , Santosh Vempala, Spectral Algorithms, Foundations and Trends® in Theoretical Computer Science, v.4 n.3–4, p.157-288, March 2009
	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999
	S. Muthukrishnan , Laxmi Parida, Towards constructing physical maps by optical mapping (extended abstract): an effective, simple, combinatorial approach, Proceedings of the first annual international conference on Computational molecular biology, p.209-219, January 20-23, 1997, Santa Fe, New Mexico, United States
	Paul Kearney , Ming Li , John Tsang , Tao Jiang, Recovering branches on the tree of life: an approximation algorithm, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.537-546, January 17-19, 1999, Baltimore, Maryland, United States
	Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems, Information and Computation, v.173 n.1, p.40-63, February 25, 2002
	Rafail Ostrovsky , Yuval Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM (JACM), v.49 n.2, p.139-156, March 2002
	Sanjeev Khanna , Rajeev Motwani, Towards a syntactic characterization of PTAS, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.329-337, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Leonard J. Schulman, Clustering for edge-cost minimization (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.547-555, May 21-23, 2000, Portland, Oregon, United States
	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, 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
	Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	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
	Penny Haxell , Brendan Nagle , Vojtěch Rödl, Integer and fractional packings in dense 3-uniform hypergraphs, Random Structures & Algorithms, v.22 n.3, p.248-310, May 2003
	Yuichi Asahiro , Refael Hassin , Kazuo Iwama, Complexity of finding dense subgraphs, Discrete Applied Mathematics, v.121 n.1-3, p.15-26, 15 September 2002
	Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSPs, Journal of Computer and System Sciences, v.67 n.2, p.212-243, September 2003
	J. Díaz , N. Do , M. J. Serna , N. C. Wormald, Bounds on the max and min bisection of random cubic and random 4-regular graphs, Theoretical Computer Science, v.307 n.3, p.531-547, 14 October 2003
	W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon, Approximation schemes for Metric Bisection and partitioning, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Gruia Călinescu , Howard Karloff , Yuval Rabani, An improved approximation algorithm for multiway cut, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.48-52, May 24-26, 1998, Dallas, Texas, 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
	Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
	Konstantin Andreev , Harald Räcke, Balanced graph partitioning, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Francis Y. L. Chin , Xiaotie Deng , Qizhi Fang , Shanfeng Zhu, Approximate and dynamic rank aggregation, Theoretical Computer Science, v.325 n.3, p.409-424, 6 October 2004
	Ming Li , Bin Ma , Lusheng Wang, On the closest string and substring problems, Journal of the ACM (JACM), v.49 n.2, p.157-171, March 2002
	W. Fernandez de la Vega , Marek Karpinski , Ravi Kannan , Santosh Vempala, Tensor decomposition and approximation schemes for constraint satisfaction problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Elena Prieto, The method of extremal structure on the k-maximum cut problem, Proceedings of the 2005 Australasian symposium on Theory of computing, p.119-126, January 01, 2005, Newcastle, Australia
	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Journal of the ACM (JACM), v.51 n.2, p.263-280, March 2004
	Christian Borgs , Jennifer Chayes , László Lovász , Vera T. Sós , Balázs Szegedy , Katalin Vesztergombi, Graph limits and parameter testing, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Béla Csaba , Marek Karpinski , Piotr Krysta, Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.74-83, January 06-08, 2002, San Francisco, California
	Frank Nielsen, On point covers of c-oriented polygons, Theoretical Computer Science, v.263 n.1-2, p.17-29, July 28 2001
	V. Rödl , M. Schacht , M. H. Siggers , N. Tokushige, Integer and fractional packings of hypergraphs, Journal of Combinatorial Theory Series B, v.97 n.2, p.245-268, March, 2007
	Nir Ailon , Noga Alon, Hardness of fully dense problems, Information and Computation, v.205 n.8, p.1117-1129, August, 2007
	Marek Karpinski , Miroslaw Kowaluk , Andrzej Lingas, Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs, Fundamenta Informaticae, v.62 n.3-4, p.369-375, August 2004
	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
	Claire Mathieu , Warren Schudy, Yet another algorithm for dense max cut: go greedy, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.176-182, January 20-22, 2008, San Francisco, California
	Maria Liazi , Ioannis Milis , Vassilis Zissimopoulos, A constant approximation algorithm for the densest k-subgraph problem on chordal graphs, Information Processing Letters, v.108 n.1, p.29-32, September, 2008
	Marek Karpinski , Warren Schudy, Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Josep Diaz , Fabrizio Grandoni , Alberto Marchetti Spaccamela, Balanced cut approximation in random geometric graphs, Theoretical Computer Science, v.410 n.27-29, p.2725-2731, June, 2009
	Petros Drineas , Ravi Kannan , Michael W. Mahoney, Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms, Random Structures & Algorithms, v.32 n.3, p.307-333, May 2008