Publication

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski
2018
Conference Papers

Abstract

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Chat with Graph Search

Learning to Remove Cuts in Integer Linear Programming

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

A ride time-oriented scheduling algorithm for dial-a-ride problems