Constant Factor Approximation for ATSP with Two Edge Weights

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently in [ 17]. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest.


Editor(s):
Louveaux, Q
Skutella, M
Published in:
Integer Programming And Combinatorial Optimization, Ipco 2016, 9682, 226-237
Presented at:
18th International Conference on Integer Programming and Combinatorial Optimization (IPCO), Liege, BELGIUM, JUN 01-03, 2016
Year:
2016
Publisher:
Cham, Springer Int Publishing Ag
ISSN:
0302-9743
ISBN:
978-3-319-33461-5
978-3-319-33460-8
Laboratories:




 Record created 2016-10-18, last modified 2018-05-09


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)