Paper Info
Title
A 4/5-Approximation Algorithm For The Maximum Traveling Salesman Problem
Abstract
In the maximum traveling salesman problem (Max TSP) we are given a complete undirected graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight. We present a fast combinatorial 4/5 - approximation algorithm for Max TSP. The previous best approximation for this problem was 7/9. The new algorithm is based on a technique of eliminating difficult subgraphs via gadgets with half-edges, a new method of edge coloring and a technique of exchanging edges.
Year
DOI
Venue
2017
10.1007/978-3-319-59250-3_15
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2017
DocType
Volume
ISSN
Conference
10328
0302-9743
Citations 
PageRank 
References 
0
0.34
12
Authors
4
Name
Order
Citations
PageRank
Szymon Dudycz1202.77
Jan Marcinkowski2473.92
Katarzyna E. Paluch39110.94
Bartosz Rybicki4434.80