Improved deterministic approximation algorithms for Max TSP |
| |
| Authors: | Zhi-Zhong Chen Yuusuke Okamoto |
| |
| Affiliation: | a Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
b Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong |
| |
| Abstract: | We present an O(n3)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically  , where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n3)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically  . Both algorithms improve on the previous bests. |
| |
| Keywords: | Approximation algorithms Graph algorithms Randomized algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
