Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
From MaRDI portal
Publication:4764340
DOI10.1137/S0895480192240226zbMath0832.90089MaRDI QIDQ4764340
Thomas Andreae, Hans-Jürgen Bandelt
Publication date: 4 May 1995
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
traveling salesmanapproximation algorithmsminimum Steiner treeperformance guaranteeanticlusteringparametrized triangle inequalityworst-case analyses of heuristics
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Discrete mathematics in relation to computer science (68R99)
Related Items (28)
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 ⋮ Performance guarantees for the TSP with a 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 ⋮ Constant factor approximation algorithm for TSP satisfying a biased triangle inequality ⋮ Triadic distance models: axiomatization and least squares representation ⋮ An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality ⋮ Minimum transversals of maximum matchings as approximate solutions to the bisection problem ⋮ On the relationship between ATSP and the cycle cover problem ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ Fixed parameter tractability of a biconnected bottleneck Steiner network problem ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ A Modern View on Stability of Approximation ⋮ The minimum-area spanning tree problem ⋮ On approximability of linear ordering and related NP-optimization problems on graphs. ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ On the two largest distance eigenvalues of graph powers ⋮ On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ Improved approximations for ordered TSP on near-metric graphs ⋮ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality ⋮ Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
This page was built for publication: Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
