On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
From MaRDI portal
Publication:5387977
DOI10.1287/moor.1060.0191zbMath1278.90328MaRDI QIDQ5387977
Moses Charikar, Michel X. Goemans, Howard J. 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
approximation algorithm; ATSP; asymmetric traveling salesman problem; Held-Karp relaxation; integrality ratio
Related Items
On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy, A simple LP relaxation for the asymmetric traveling salesman problem, Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems, An Improved Integrality Gap for Asymmetric TSP Paths, A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem