Christos H. Papadimitriou
- 1.N. Alon, "On the edge-expansion of graphs," Combinatorics, Probability and Computing, 6, (1997), 145-152. Google Scholar
Digital Library
- 2.A. Amit and N. Linial, "Random Graph Coverings," manuscript.Google Scholar
- 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.Google Scholar
- 4.P. Berman and M. Karpinski, "On some tighter inapproximability results," Tech. Rep. TR98-029, ECCC, 1998. Google ScholarDigital Library
- 5.B. Bollobis, "The isoperimetric number of random regular graphs," Europ. J. of Combinatorics, 9, 241-244, 1988. Google ScholarDigital Library
- 6.R. Carr and S. Vempala, "Towards a 4/3 approximation for the asymmetric traveling salesman problem," Proc. of ACM-SIAM SODA 2000. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 8.J. H~stad, "Some optimal inapproximability results," Proc. of ACM STOC 1997. Google ScholarDigital Library
- 9.J. H&stad, "Clique is hard to approximate within nl-~,'' Proc. of IEEE FOCS 1996. Google ScholarDigital Library
- 10.S. Khanna, M. Sudan, and D.P. Williamson, "A complete classification of the approximability of maximization problems derived from Boolean Constraint satisfaction," Proc. of ACM STOC 1997. Google ScholarDigital Library
- 11.L. Engebretsen, "An Explicit Lower Bound for TSP with Distances One and Two," Proc. of STACS 1999. Google ScholarDigital Library
- 12.C. H. Papadimitriou and M. Yannakakis, "The traveling salesman problem with distances one and two," Math of OR, 18(1), 1-11, 1993. Google ScholarDigital Library
- 13.L. Trevisan, G. Sorkin, M. Sudan, D. Williamson, "Gadgets, approximation and linear programming," Proc. of IEEE FOCS 1996. Google ScholarDigital Library
Index Terms
- On the approximability of the traveling salesman problem (extended abstract)
Recommendations
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingThe Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+µ)-approximation to the optimal tour, for any fixed µ>0, in TSP instances ...
Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
AbstractWe consider the geometric version of the well-known Generalized Traveling Salesman Problem introduced in 2015 by Bhattacharya et al. that is called the Euclidean Generalized Traveling Salesman Problem in Grid Clusters (EGTSP-GC). They proved the ...
Comments