Buffer overflow management in QoS switches
Alexander Kesselman, Zvi Lotker, et al.
STOC 2001
The maximum asymmetric traveling salesperson problem, also known as the taxicab rip-off problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with nonnegative weights. We propose a polynomial time approximation algorithm for the problem with a 5/8 approximation guarantee. This (1) improves upon the approximation factors of previous results and (2) presents a simpler solution to the previously fairly involved algorithms. Our solution uses a simple linear programming formulation. Previous solutions were combinatorial. We make use of the linear programming in a novel manner and strengthen the path-coloring method originally proposed in [S. R. Kosaraju, J. K. Park, and C. Stein, Long tours and short superstrings, in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 166-177].
Alexander Kesselman, Zvi Lotker, et al.
STOC 2001
Nikhil Bansal, Don Coppersmiths, et al.
SIAM Journal on Computing
Marcin Bienkowski, Jarosław Byrka, et al.
Journal of Scheduling
Lisa Fleischer, Michel X. Goemans, et al.
SODA 2006