Improved deterministic approximation algorithms for max TSP

DOI10.1016/j.ipl.2005.03.011zbMath1185.68851OpenAlexW2069381123MaRDI QIDQ1041779

Zhi-Zhong Chen, Lusheng Wang, Yuusuke Okamoto

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.03.011

zbMATH Keywords

graph algorithmsapproximation algorithmsrandomized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (12)

An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem ⋮ Minimum-Weight Cycle Covers and Their Approximability ⋮ Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems ⋮ A better differential approximation ratio for symmetric TSP ⋮ Approximating Multi-criteria Max-TSP ⋮ A 0.5358-approximation for Bandpass-2 ⋮ Improved approximation algorithms for metric MaxTSP ⋮ On the maximum TSP with \(\gamma\)-parameterized triangle inequality ⋮ Unnamed Item ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ Minimum-weight cycle covers and their approximability ⋮ Reoptimization of minimum and maximum traveling salesman's tours

Cites Work

• Unnamed Item
• Unnamed Item
• An approximation algorithm for the maximum traveling salesman problem
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Parallel constructions of maximal path sets and applications to short superstrings
• Better approximations for max TSP
• A \(\frac78\)-approximation algorithm for metric Max TSP

This page was built for publication: Improved deterministic approximation algorithms for max TSP