scientific article; zbMATH DE number 1500530

MaRDI QIDQ4501548zbMATH OpenFDO

Authors Juraj Hromkovič, Ralf Klasing, Sebastian Seibert, Walter Unger, Hans-Joachim Böckenhauer

Publication date 27 January 2004

zbMATH Keywords

approximation algorithmstraveling Salesman problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Approximation algorithms for the TSP with sharpened triangle inequality
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• Improved Approximation Lower Bounds for TSP with Distances One and Two

Cited in

(37)

• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Approximating the metric TSP in linear time
• Structural properties of hard metric TSP inputs (extended abstract)
• New inapproximability bounds for TSP
• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• scientific article; zbMATH DE number 4095236 (Why is no real title available?)
• Estimating the Held-Karp lower bound for the geometric TSP
• On the approximation ratio of the path matching Christofides algorithm
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• On \(k\)-connectivity problems with sharpened triangle inequality
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
• On the Approximation Hardness of Some Generalizations of TSP
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Algorithms for the metric ring star problem with fixed edge-cost ratio
• A Modern View on Stability of Approximation
• An explicit lower bound for TSP with distances one and two
• Approximation Algorithms for the Traveling Salesman Problem with Range Condition
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
• A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
• Constant factor approximation algorithm for TSP satisfying a biased triangle inequality
• Improved Approximation Lower Bounds for TSP with Distances One and Two
• Weighted amplifiers and inapproximability results for travelling salesman problem
• Analysis of a near-metric TSP approximation algorithm
• Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
• A (slightly) improved approximation algorithm for metric TSP
• Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
• Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality
• On the Hardness of Reoptimization
• A better differential approximation ratio for symmetric TSP
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Ordered spatial sampling by means of the traveling salesman problem
• On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
• Approximation algorithms for the traveling salesman problem
• Approximation algorithms for the TSP with sharpened triangle inequality
• Approximating the Metric TSP in Linear Time

This page was built for publication:

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