On the Integrality Ratio for the Asymmetric Traveling Salesman Problem

DOI10.1287/MOOR.1060.0191MaRDI QIDQ5387977zbMATH OpenOpenAlexFDO

Authors Michel X. Goemans, Moses Charikar, Howard Karloff

Publication date 27 May 2008

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/073d88c0a3f2f96180c42a0c9f8407fe1b24afc9

zbMATH Keywords

approximation algorithmasymmetric traveling salesman problemATSPHeld-Karp relaxationintegrality ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 4039668
• On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
• On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
• An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
• scientific article; zbMATH DE number 5899262
• A note on the complexity of the asymmetric traveling salesman problem
• A note on the approximation of the asymmetric traveling salesman problem.

Cited in

(13)

• A constant-factor approximation for directed latency in quasi-polynomial time
• Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems
• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
• On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
• scientific article; zbMATH DE number 6347354 (Why is no real title available?)
• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
• A simple LP relaxation for the asymmetric traveling salesman problem
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Technical Note—On Traveling Salesman Games with Asymmetric Costs
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
• Polyhedral techniques in combinatorial optimization: matchings and tours
• On the integrality gap of small asymmetric traveling salesman problems: a polyhedral and computational approach

This page was built for publication: On the Integrality Ratio for the Asymmetric Traveling Salesman Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387977)