scientific article; zbMATH DE number 1500530

zbMATH Open1028.90044MaRDI QIDQ4501548FDOQ4501548

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

Publication date: 27 January 2004

Title of this publication is not available (Why is that?)

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

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)

Cited In (38)

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

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)