On the approximability of the traveling salesman problem (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the approximability of the traveling salesman problem (extended abstract)

Full text

Pdf (553 KB)

Source

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

Portland, Oregon, United States

Pages: 126 - 133

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Christos H. Papadimitriou	Computer Science Department, U.C. Berkeley
Santosh Vempala	Department of Mathematics and Laboratory for Computer Science, MIT

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 42, Citation Count: 11

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/335305.335320 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	Noga Alon, On the Edge-Expansion of Graphs, Combinatorics, Probability and Computing, v.6 n.2, p.145-152, June 1997 [doi>10.1017/S096354839700299X]
	2	A. Amit and N. Linial, "Random Graph Coverings," manuscript.
	3	S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, "Proof verification and the intractability of approximation problems," Proc, of IEEE FOCS 1992.
	4	Marek Karpinski , Piotr Berman, On Some Tighter Inapproximability Results, Further Improvements, University of Bonn, 1998
	5	Béla Bollobás, The isoperimetric number of random regular graphs, European Journal of Combinatorics, v.9 n.3, p.241-244, May 1988
	6	Robert D. Carr , Santosh Vempala, Towards a 4/3 approximation for the asymmetric traveling salesman problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.116-125, January 09-11, 2000, San Francisco, California, United States
	7	A. Frieze, G. Galbiati, and F. Maffioli, "On the worst-case performance of some algorithms for the asymmetric traveling salesman problem," Networks 12, 23-39, 1982.
	8	Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
	9	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
	10	Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258538]
	11	L. Engebretsen, "An Explicit Lower Bound for TSP with Distances One and Two," Proc. of STACS 1999.
	12	Christos H. Papadimitriou , Mihalis Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, v.18 n.1, p.1-11, Feb. 1993 [doi>10.1287/moor.18.1.1]
	13	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

CITED BY 12

	Fedor V. Fomin , Andrej Lilngas, Approximation algorithms for time-dependent orienteering, Information Processing Letters, v.83 n.2, p.57-62, 31 July 2002
	Cristina Bazgan , Refael Hassin , Jérôme Monnot, Approximation algorithms for some vehicle routing problems, Discrete Applied Mathematics, v.146 n.1, p.27-42, 15 February 2005
	Martin Thimm, On the approximability of the Steiner tree problem, Theoretical Computer Science, v.295 n.1-3, p.387-402, 24 February 2003
	Eric Angel , Evripidis Bampis , Laurent Gourvès, Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem, Theoretical Computer Science, v.310 n.1-3, p.135-146, 01 January 2004
	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
	Shmuel Safra , Oded Schwartz, On the complexity of approximating tsp with neighborhoods and related problems, Computational Complexity, v.14 n.4, p.281-307, March 2006
	Miroslav Chlebík , Janka Chlebíková, Complexity of approximating bounded variants of optimization problems, Theoretical Computer Science, v.354 n.3, p.320-338, 4 April 2006
	Lars Engebretsen , Marek Karpinski, TSP with bounded metrics, Journal of Computer and System Sciences, v.72 n.4, p.509-546, June 2006
	Amin Coja-Oghlan , Sven O. Krumke , Till Nierhoff, A heuristic for the Stacker Crane Problem on trees which is almost surely exact, Journal of Algorithms, v.61 n.1, p.1-19, September, 2006
	Moses Charikar , Michel X. Goemans , Howard Karloff, On the Integrality Ratio for the Asymmetric Traveling Salesman Problem, Mathematics of Operations Research, v.31 n.2, p.245-252, February 2006
	Vardges Melkonian, LP-based solution methods for the asymmetric TSP, Information Processing Letters, v.101 n.6, p.233-238, March, 2007
	Miroslav Chlebík , Janka Chlebíková, The Steiner tree problem on graphs: Inapproximability results, Theoretical Computer Science, v.406 n.3, p.207-214, October, 2008