An Improved Randomized Approximation Algorithm for Max TSP期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

An Improved Randomized Approximation Algorithm for Max TSP

Authors:	Email author" target="_blank">Zhi-Zhong?Chen Email author Lusheng?Wang

Institution:	(1) Department of Mathematical Sciences, Tokyo Denki University, Hatoyama Saitama, 350-0394, Japan;(2) Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong

Abstract:	We present an O(n³)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically $\frac{251}{331}$ , where n is the number of vertices in the input (undirected) graph. This improves the previous best.Part of work done while visiting City University of Hong Kong.

Keywords:	Max TSP approximation algorithms randomized algorithms graph algorithms
本文献已被 SpringerLink 等数据库收录！