On the Integrality Ratio for the Asymmetric Traveling Salesman Problem

DOI10.1287/moor.1060.0191zbMath1278.90328OpenAlexW2123701486MaRDI QIDQ5387977

Michel X. Goemans, Howard J. Karloff, Moses Charikar

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 algorithmATSPasymmetric traveling salesman problemHeld-Karp relaxationintegrality ratio

Mathematics Subject Classification ID

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

Related Items (11)

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ An Improved Integrality Gap for Asymmetric TSP Paths ⋮ Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems ⋮ A simple LP relaxation for the asymmetric traveling salesman problem ⋮ Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ The asymmetric traveling salesman path LP has constant integrality ratio ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

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