Approximation hardness of TSP with bounded metrics

DOI10.1007/3-540-48224-5_17MaRDI QIDQ4535019zbMATH OpenFDO

Authors Lars Engebretsen, Marek Karpinski

Publication date 12 June 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2076/20760201

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• TSP with bounded metrics
• On the Approximation Hardness of Some Generalizations of TSP
• Approximating TSP on metrics with bounded global growth
• On the approximation hardness of dense TSP and other path problems
• A (slightly) improved approximation algorithm for metric TSP
• Approximating the Metric TSP in Linear Time
• Approximating the metric TSP in linear time
• A deterministic better-than-3/2 approximation algorithm for metric TSP
• Truly tight bounds for TSP heuristics
• Approximation hardness of Travelling Salesman via weighted amplifiers

Cited in

(26)

• Estimating the Held-Karp lower bound for the geometric TSP
• On the approximation hardness of dense TSP and other path problems
• Affine reductions for LPs and SDPs
• Approximation algorithms for some vehicle routing problems
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example
• Differential approximation results for the traveling salesman problem with distances 1 and 2
• When the greedy algorithm fails
• TSP with bounded metrics
• New inapproximability bounds for TSP
• Approximating TSP on metrics with bounded global growth
• Towards better inapproximability bounds for TSP: a challenge of global dependencies
• Differential approximation results for the traveling salesman and related problems
• Restricted common superstring and restricted common supersequence
• On the Complexity of the Metric TSP under Stability Considerations
• On the approximability of the traveling salesman problem (extended abstract)
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Differential approximation of NP-hard problems with equal size feasible solutions
• New inapproximability bounds for TSP
• On the \({\mathcal {H}}\)-free extension complexity of the TSP
• A (1+\varepsilon)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
• On the Approximation Hardness of Some Generalizations of TSP
• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
• From Chinese postman to salesman and beyond: shortest tour -covering all points on all edges
• From Chinese postman to salesman and beyond. II: Inapproximability and parameterized complexity
• Cooperative TSP

This page was built for publication: Approximation hardness of TSP with bounded metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4535019)