The parameterized approximability of TSP with deadlines
From MaRDI portal
Publication:2464332
DOI10.1007/s00224-007-1347-xzbMath1148.68052OpenAlexW2091368663MaRDI QIDQ2464332
Joachim Kupke, Joachim Kneis, Hans-Joachim Böckenhauer, Juraj Hromkovič
Publication date: 19 December 2007
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: http://doc.rero.ch/record/316215/files/224_2007_Article_1347.pdf
Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (14)
From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times ⋮ Adversarial patrolling with spatially uncertain alarm signals ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Cyclic-routing of unmanned aerial vehicles ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ Reoptimization of the metric deadline TSP ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Reoptimization of the Metric Deadline TSP ⋮ On the Hardness of Reoptimization ⋮ Deadline TSP ⋮ Approximation hardness of deadline-TSP reoptimization ⋮ Moderately exponential time and fixed parameter approximation algorithms
This page was built for publication: The parameterized approximability of TSP with deadlines
