An improved randomized approximation algorithm for Max TSP

DOI10.1007/s10878-005-1779-7zbMath1093.90046OpenAlexW2054136337MaRDI QIDQ2576776

Lusheng Wang, Zhi-Zhong Chen

Publication date: 14 December 2005

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-005-1779-7

zbMATH Keywords

graph algorithmsapproximation algorithmsrandomized algorithmsMax TSP

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (5)

Parameterized and approximation algorithms for finding two disjoint matchings ⋮ Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems ⋮ Improved approximation algorithms for metric MaxTSP ⋮ Approximation algorithms for maximum latency and partial cycle cover ⋮ Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Cites Work

• Unnamed Item
• An approximation algorithm for the maximum traveling salesman problem
• Better approximations for max TSP
• A \(\frac78\)-approximation algorithm for metric Max TSP
• Approximating Capacitated Routing and Delivery Problems

This page was built for publication: An improved randomized approximation algorithm for Max TSP