scientific article; zbMATH DE number 1500530
From MaRDI portal
Publication:4501548
zbMath1028.90044MaRDI QIDQ4501548
Walter Unger, Sebastian Seibert, Juraj Hromkovič, Ralf Klasing, Hans-Joachim Böckenhauer
Publication date: 27 January 2004
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Approximation Algorithms for the Traveling Salesman Problem with Range Condition ⋮ Improved Lower Bounds on the Approximability of the Traveling Salesman Problem ⋮ On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality ⋮ Approximation algorithms for the TSP with sharpened triangle inequality ⋮ On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality ⋮ Ordered spatial sampling by means of the traveling salesman problem ⋮ Weighted amplifiers and inapproximability results for travelling salesman problem ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ A Modern View on Stability of Approximation ⋮ Approximating the metric TSP in linear time ⋮ New inapproximability bounds for TSP ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ On the Hardness of Reoptimization ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ Approximation algorithms for multi-criteria traveling salesman problems ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
