Deterministic 7/8-approximation for the metric maximum TSP

DOI10.1016/j.tcs.2009.07.051zbMath1209.90359OpenAlexW3021112015MaRDI QIDQ1034619

Łukasz Kowalik, Marcin Mucha

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.051

zbMATH Keywords

matchingapproximationcycle covermaximum TSP

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem ⋮ Truthful Mechanisms for Matching and Clustering in an Ordinal World ⋮ Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems ⋮ On the maximum TSP with \(\gamma\)-parameterized triangle inequality ⋮ An improved approximation algorithm for the maximum TSP ⋮ Approximation of the double traveling salesman problem with multiple stacks

Cites Work

• A \(\frac78\)-approximation algorithm for metric Max TSP
• 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality
• Algorithms – ESA 2005
• Unnamed Item