| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436371 | Theoretical Computer Science | 2008 | 8 Pages |
Abstract
In this paper, we study the approximability properties of symmetric TSP under an approximation measure called the differential ratio. More precisely, we improve up to 3/4−ε (for any ε>0) the best differential ratio of 2/3 known so far, given in Hassin and Khuller, [R. Hassin, S. Khuller, z-approximations, J. Algorithms, 41 (2) (2001) 429–442].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
