An improved randomized approximation algorithm for max TSP

Zhi-Zhong Chen; Lusheng Wang

doi:10.1007/s10878-005-1779-7

An improved randomized approximation algorithm for max TSP

Zhi-Zhong Chen
, Lusheng Wang

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

9 Citations (Scopus)

Abstract

We present an O(n ³)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where n is the number of vertices in the input (undirected) graph. This improves the previous best. © 2005 Springer Science + Business Media, Inc.

Original language	English
Pages (from-to)	401-432
Journal	Journal of Combinatorial Optimization
Volume	9
Issue number	4
DOIs	https://doi.org/10.1007/s10878-005-1779-7
Publication status	Published - Jun 2005

Research Keywords

Approximation algorithms
Graph algorithms
Max TSP
Randomized algorithms

Access Output

10.1007/s10878-005-1779-7

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{e20b988b204d43188f344576fff217b3,

title = "An improved randomized approximation algorithm for max TSP",

abstract = "We present an O(n 3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where n is the number of vertices in the input (undirected) graph. This improves the previous best. {\textcopyright} 2005 Springer Science + Business Media, Inc.",

keywords = "Approximation algorithms, Graph algorithms, Max TSP, Randomized algorithms",

author = "Zhi-Zhong Chen and Lusheng Wang",

year = "2005",

month = jun,

doi = "10.1007/s10878-005-1779-7",

language = "English",

volume = "9",

pages = "401--432",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - An improved randomized approximation algorithm for max TSP

AU - Chen, Zhi-Zhong

AU - Wang, Lusheng

PY - 2005/6

Y1 - 2005/6

N2 - We present an O(n 3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where n is the number of vertices in the input (undirected) graph. This improves the previous best. © 2005 Springer Science + Business Media, Inc.

AB - We present an O(n 3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where n is the number of vertices in the input (undirected) graph. This improves the previous best. © 2005 Springer Science + Business Media, Inc.

KW - Approximation algorithms

KW - Graph algorithms

KW - Max TSP

KW - Randomized algorithms

UR - https://www.scopus.com/pages/publications/23944508242

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-23944508242&origin=recordpage

U2 - 10.1007/s10878-005-1779-7

DO - 10.1007/s10878-005-1779-7

M3 - RGC 21 - Publication in refereed journal

SN - 1382-6905

VL - 9

SP - 401

EP - 432

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

An improved randomized approximation algorithm for max TSP

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this