Paper Info
Title
The asymmetric traveling salesman problem on graphs with bounded genus
Abstract
We give a constant factor approximation algorithm for the asymmetric traveling salesman problem when the support graph of the solution of the Held-Karp linear programming relaxation has bounded orientable genus.
Year
DOI
Venue
2011
10.5555/2133036.2133111
Clinical Orthopaedics and Related Research
Keywords
Field
DocType
orientable genus,constant factor approximation algorithm,salesman problem,held-karp linear programming relaxation,bounded genus,support graph,linear programming relaxation,randomized algorithms,leader election,distributed computing
Bottleneck traveling salesman problem,Randomized algorithm,Approximation algorithm,Discrete mathematics,Combinatorics,Travelling salesman problem,Christofides algorithm,2-opt,Linear programming relaxation,Mathematics,Bounded function
Conference
Volume
ISBN
Citations 
abs/0909.2
978-1-61197-251-1
15
PageRank 
References 
Authors
0.74
21
2
Name
Order
Citations
PageRank
Shayan Oveis Gharan132326.63
Amin Saberi22824224.27