Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
From MaRDI portal
Publication:4764340
DOI10.1137/S0895480192240226zbMath0832.90089MaRDI QIDQ4764340
Hans-Jürgen Bandelt, Thomas Andreae
Publication date: 4 May 1995
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
traveling salesman; approximation algorithms; minimum Steiner tree; performance guarantee; anticlustering; parametrized triangle inequality; worst-case analyses of heuristics
90C35: Programming involving graphs or networks
90C27: Combinatorial optimization
68R99: Discrete mathematics in relation to computer science
Related Items
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Approximation Algorithms for the Traveling Salesman Problem with Range Condition, Improved Lower Bounds on the Approximability of the Traveling Salesman Problem, On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality, Triadic distance models: axiomatization and least squares representation, On approximability of linear ordering and related NP-optimization problems on graphs., Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem., Minimum transversals of maximum matchings as approximate solutions to the bisection problem, On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
