An improved approximation algorithm for the bandpass-2 problem

Zhi-Zhong Chen; Lusheng Wang

doi:10.1007/978-3-642-31770-5_17

An improved approximation algorithm for the bandpass-2 problem

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

8 Citations (Scopus)

Abstract

The bandpass-2 problem (Bandpass-2, for short) is a generalization of the maximum traveling salesman problem (Max TSP, for short). Of particular interest is the difference between the two problems, where the edge weights in Bandpass-2 are dynamic rather than given at the front. A trivial approximation algorithm for Bandpass-2 can achieve a ratio of 0.5. Recently, Tong et al. [19] have presented a nontrivial approximation algorithm for Bandpass-2 that achieves a ratio of 21/40. In this paper, we present a new approximation algorithm that achieves a ratio of 0.5318. © 2012 Springer-Verlag.

Original language	English
Title of host publication	Combinatorial Optimization and Applications
Subtitle of host publication	6th International Conference, COCOA 2012, Proceedings
Publisher	Springer Verlag
Pages	188-199
Volume	7402 LNCS
ISBN (Print)	9783642317699
DOIs	https://doi.org/10.1007/978-3-642-31770-5_17
Publication status	Published - 2012
Event	6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012) - Banff, AB, Canada Duration: 5 Aug 2012 → 9 Aug 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7402 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)
Abbreviated title	COCOA 2012
Place	Canada
City	Banff, AB
Period	5/08/12 → 9/08/12

Research Keywords

approximation algorithm
Bandpass-2 problem
maximum weight 2-matching
maximum weight matching
worst-case performance ratio

Access Output

10.1007/978-3-642-31770-5_17

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, Z.-Z., & Wang, L. (2012). An improved approximation algorithm for the bandpass-2 problem. In Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Proceedings (Vol. 7402 LNCS, pp. 188-199). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7402 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-31770-5_17

Chen, Zhi-Zhong ; Wang, Lusheng. / An improved approximation algorithm for the bandpass-2 problem. Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Proceedings. Vol. 7402 LNCS Springer Verlag, 2012. pp. 188-199 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{71322bb0c03c4c818ca783318f8a9aa2,

title = "An improved approximation algorithm for the bandpass-2 problem",

abstract = "The bandpass-2 problem (Bandpass-2, for short) is a generalization of the maximum traveling salesman problem (Max TSP, for short). Of particular interest is the difference between the two problems, where the edge weights in Bandpass-2 are dynamic rather than given at the front. A trivial approximation algorithm for Bandpass-2 can achieve a ratio of 0.5. Recently, Tong et al. [19] have presented a nontrivial approximation algorithm for Bandpass-2 that achieves a ratio of 21/40. In this paper, we present a new approximation algorithm that achieves a ratio of 0.5318. {\textcopyright} 2012 Springer-Verlag.",

keywords = "approximation algorithm, Bandpass-2 problem, maximum weight 2-matching, maximum weight matching, worst-case performance ratio",

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

year = "2012",

doi = "10.1007/978-3-642-31770-5_17",

language = "English",

isbn = "9783642317699",

volume = "7402 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "188--199",

booktitle = "Combinatorial Optimization and Applications",

address = "Germany",

note = "6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012), COCOA 2012 ; Conference date: 05-08-2012 Through 09-08-2012",

}

Chen, Z-Z & Wang, L 2012, An improved approximation algorithm for the bandpass-2 problem. in Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Proceedings. vol. 7402 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7402 LNCS, Springer Verlag, pp. 188-199, 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012), Banff, AB, Canada, 5/08/12. https://doi.org/10.1007/978-3-642-31770-5_17

An improved approximation algorithm for the bandpass-2 problem. / Chen, Zhi-Zhong; Wang, Lusheng.
Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Proceedings. Vol. 7402 LNCS Springer Verlag, 2012. p. 188-199 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7402 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - An improved approximation algorithm for the bandpass-2 problem

AU - Chen, Zhi-Zhong

AU - Wang, Lusheng

PY - 2012

Y1 - 2012

N2 - The bandpass-2 problem (Bandpass-2, for short) is a generalization of the maximum traveling salesman problem (Max TSP, for short). Of particular interest is the difference between the two problems, where the edge weights in Bandpass-2 are dynamic rather than given at the front. A trivial approximation algorithm for Bandpass-2 can achieve a ratio of 0.5. Recently, Tong et al. [19] have presented a nontrivial approximation algorithm for Bandpass-2 that achieves a ratio of 21/40. In this paper, we present a new approximation algorithm that achieves a ratio of 0.5318. © 2012 Springer-Verlag.

AB - The bandpass-2 problem (Bandpass-2, for short) is a generalization of the maximum traveling salesman problem (Max TSP, for short). Of particular interest is the difference between the two problems, where the edge weights in Bandpass-2 are dynamic rather than given at the front. A trivial approximation algorithm for Bandpass-2 can achieve a ratio of 0.5. Recently, Tong et al. [19] have presented a nontrivial approximation algorithm for Bandpass-2 that achieves a ratio of 21/40. In this paper, we present a new approximation algorithm that achieves a ratio of 0.5318. © 2012 Springer-Verlag.

KW - approximation algorithm

KW - Bandpass-2 problem

KW - maximum weight 2-matching

KW - maximum weight matching

KW - worst-case performance ratio

UR - http://www.scopus.com/inward/record.url?scp=84864986118&partnerID=8YFLogxK

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

U2 - 10.1007/978-3-642-31770-5_17

DO - 10.1007/978-3-642-31770-5_17

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783642317699

VL - 7402 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 188

EP - 199

BT - Combinatorial Optimization and Applications

PB - Springer Verlag

T2 - 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)

Y2 - 5 August 2012 through 9 August 2012

ER -

Chen ZZ, Wang L. An improved approximation algorithm for the bandpass-2 problem. In Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Proceedings. Vol. 7402 LNCS. Springer Verlag. 2012. p. 188-199. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-31770-5_17

An improved approximation algorithm for the bandpass-2 problem

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this