An Improved Integrality Gap for Asymmetric TSP Paths

DOI10.1287/moor.2015.0752zbMath1371.90120arXiv1302.3145OpenAlexW2570390297MaRDI QIDQ3186524

Zachary Friggstad, Anupam Gupta, Mohit Singh

Publication date: 10 August 2016

Published in: Mathematics of Operations Research, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.3145

zbMATH Keywords

linear programmingtraveling salesmanintegrality gapsthin spanning trees

Mathematics Subject Classification ID

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

Related Items (3)

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ The asymmetric traveling salesman path LP has constant integrality ratio

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Traveling salesman path problems
• The Directed Minimum Latency Problem
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• A new approach to the minimum cut problem
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• Improving christofides' algorithm for the s-t path TSP

This page was built for publication: An Improved Integrality Gap for Asymmetric TSP Paths