Improved deterministic approximation algorithms for Max TSP

Zhi-Zhong Chen; Yuusuke Okamoto; Lusheng Wang

doi:10.1016/j.ipl.2005.03.011

Improved deterministic approximation algorithms for Max TSP

Zhi-Zhong Chen
, Yuusuke Okamoto
, Lusheng Wang

Department of Computer Science

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

32 Citations (Scopus)

Abstract

We present an O(n3)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 6181, 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 1720. Both algorithms improve on the previous bests. © 2005 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	333-342
Journal	Information Processing Letters
Volume	95
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2005.03.011
Publication status	Published - 31 Jul 2005

Research Keywords

Approximation algorithms
Graph algorithms
Randomized algorithms

Access Output

10.1016/j.ipl.2005.03.011

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{ea1710a3c96040b2afaf362e0c52838c,

title = "Improved deterministic approximation algorithms for Max TSP",

abstract = "We present an O(n3)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 6181, 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 1720. Both algorithms improve on the previous bests. {\textcopyright} 2005 Elsevier B.V. All rights reserved.",

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

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

year = "2005",

month = jul,

day = "31",

doi = "10.1016/j.ipl.2005.03.011",

language = "English",

volume = "95",

pages = "333--342",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Improved deterministic approximation algorithms for Max TSP

AU - Chen, Zhi-Zhong

AU - Okamoto, Yuusuke

AU - Wang, Lusheng

PY - 2005/7/31

Y1 - 2005/7/31

N2 - We present an O(n3)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 6181, 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 1720. Both algorithms improve on the previous bests. © 2005 Elsevier B.V. All rights reserved.

AB - We present an O(n3)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 6181, 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 1720. Both algorithms improve on the previous bests. © 2005 Elsevier B.V. All rights reserved.

KW - Approximation algorithms

KW - Graph algorithms

KW - Randomized algorithms

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

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

U2 - 10.1016/j.ipl.2005.03.011

DO - 10.1016/j.ipl.2005.03.011

M3 - RGC 21 - Publication in refereed journal

SN - 0020-0190

VL - 95

SP - 333

EP - 342

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Improved deterministic approximation algorithms for Max TSP

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this