Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems

DOI10.1016/j.orl.2009.01.011zbMath1167.90621OpenAlexW1984450612MaRDI QIDQ833572

Markus Bläser, L. Shankar Ram, M. I. Sviridenko

Publication date: 14 August 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2009.01.011

zbMATH Keywords

approximation algorithmtraveling salesman problemcycle coverblossom inequalities

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem ⋮ Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization.
• A \(\frac78\)-approximation algorithm for metric Max TSP
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• Approximating Capacitated Routing and Delivery Problems
• Rotations of Periodic Strings and Short Superstrings
• A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP
• The Traveling Salesman Problem with Distances One and Two
• An -approximation algorithm for the asymmetric maximum TSP
• Algorithms – ESA 2005
• Integer Programming and Combinatorial Optimization

This page was built for publication: Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems