|
|||||
|
|
An improved upper bound for the TSP in cubic 3-edge-connected graphs |
|
| Authors: | David Gamarnik Maxim Sviridenko |
| Institution: | a Department of Computer Science, Bar Ilan University, Room 323, Mailbox 50, Ramat Gan 52900, Israel b IBM T. J. Watson Research Center, Yorktown Heights, P.O. Box 218, NY 10598, USA |
| Abstract: | We consider the travelling salesman problem (TSP) problem on (the metric completion of) 3-edge-connected cubic graphs. These graphs are interesting because of the connection between their optimal solutions and the subtour elimination LP relaxation. Our main result is an approximation algorithm better than the 3/2-approximation algorithm for TSP in general. |
| Keywords: | Approximation algorithms Travelling salesman problem Graphs Regular graphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |