| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428868 | Information Processing Letters | 2007 | 6 Pages |
Abstract
We consider an LP relaxation for ATSP. We introduce concepts of high-value and high-flow cycles in LP basic solutions and show that the existence of this kind of cycles would lead to constant-factor approximation algorithms for ATSP. The existence of high-flow cycles is motivated by computational results and theoretical observations.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
