An improved approximation algorithm for the bandpass problem

Weitian Tong; Randy Goebel; Wei Ding; Guohui Lin

doi:10.1007/978-3-642-29700-7_32

An improved approximation algorithm for the bandpass problem

Weitian Tong, Randy Goebel, Wei Ding, Guohui Lin

Computer Science

Research output: Contribution to book or proceeding › Conference article › peer-review

3 Scopus citations

Abstract

The general Bandpass-B problem is NP-hard and can be approximated by a reduction into the B-set packing problem, with a worst case performance ratio of O(B ²). When B = 2, a maximum weight matching gives a 2-approximation to the problem. The Bandpass-2 problem, or simply the Bandpass problem, can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present in this paper a -approximation algorithm for the Bandpass problem, which is the first improvement over the simple maximum weight matching based 2-approximation algorithm.

Original language	English
Title of host publication	Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings
Pages	351-358
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-642-29700-7_32
State	Published - 2012
Event	6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012 - Beijing, China Duration: May 14 2012 → May 16 2012

Publication series

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

Conference

Conference	6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012
Country/Territory	China
City	Beijing
Period	05/14/12 → 05/16/12

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Keywords

approximation algorithm
Bandpass problem
edge coloring
maximum weight matching
worst case performance ratio

Access to Document

10.1007/978-3-642-29700-7_32

Cite this

Tong, W., Goebel, R., Ding, W., & Lin, G. (2012). An improved approximation algorithm for the bandpass problem. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings (pp. 351-358). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7285 LNCS). https://doi.org/10.1007/978-3-642-29700-7_32

Tong, Weitian ; Goebel, Randy ; Ding, Wei et al. / An improved approximation algorithm for the bandpass problem. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings. 2012. pp. 351-358 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{044d912896b544fa8129c4da2045c0ca,

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

abstract = "The general Bandpass-B problem is NP-hard and can be approximated by a reduction into the B-set packing problem, with a worst case performance ratio of O(B 2). When B = 2, a maximum weight matching gives a 2-approximation to the problem. The Bandpass-2 problem, or simply the Bandpass problem, can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present in this paper a -approximation algorithm for the Bandpass problem, which is the first improvement over the simple maximum weight matching based 2-approximation algorithm.",

keywords = "approximation algorithm, Bandpass problem, edge coloring, maximum weight matching, worst case performance ratio",

author = "Weitian Tong and Randy Goebel and Wei Ding and Guohui Lin",

year = "2012",

doi = "10.1007/978-3-642-29700-7_32",

language = "English",

isbn = "9783642296994",

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

pages = "351--358",

booktitle = "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings",

note = "6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012 ; Conference date: 14-05-2012 Through 16-05-2012",

}

Tong, W, Goebel, R, Ding, W & Lin, G 2012, An improved approximation algorithm for the bandpass problem. in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7285 LNCS, pp. 351-358, 6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012, Beijing, China, 05/14/12. https://doi.org/10.1007/978-3-642-29700-7_32

An improved approximation algorithm for the bandpass problem. / Tong, Weitian; Goebel, Randy; Ding, Wei et al.
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings. 2012. p. 351-358 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7285 LNCS).

Research output: Contribution to book or proceeding › Conference article › peer-review

TY - GEN

T1 - An improved approximation algorithm for the bandpass problem

AU - Tong, Weitian

AU - Goebel, Randy

AU - Ding, Wei

AU - Lin, Guohui

PY - 2012

Y1 - 2012

N2 - The general Bandpass-B problem is NP-hard and can be approximated by a reduction into the B-set packing problem, with a worst case performance ratio of O(B 2). When B = 2, a maximum weight matching gives a 2-approximation to the problem. The Bandpass-2 problem, or simply the Bandpass problem, can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present in this paper a -approximation algorithm for the Bandpass problem, which is the first improvement over the simple maximum weight matching based 2-approximation algorithm.

AB - The general Bandpass-B problem is NP-hard and can be approximated by a reduction into the B-set packing problem, with a worst case performance ratio of O(B 2). When B = 2, a maximum weight matching gives a 2-approximation to the problem. The Bandpass-2 problem, or simply the Bandpass problem, can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present in this paper a -approximation algorithm for the Bandpass problem, which is the first improvement over the simple maximum weight matching based 2-approximation algorithm.

KW - approximation algorithm

KW - Bandpass problem

KW - edge coloring

KW - maximum weight matching

KW - worst case performance ratio

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

U2 - 10.1007/978-3-642-29700-7_32

DO - 10.1007/978-3-642-29700-7_32

M3 - Conference article

AN - SCOPUS:84861219249

SN - 9783642296994

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

SP - 351

EP - 358

BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings

T2 - 6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012

Y2 - 14 May 2012 through 16 May 2012

ER -

Tong W, Goebel R, Ding W, Lin G. An improved approximation algorithm for the bandpass problem. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings. 2012. p. 351-358. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-29700-7_32

An improved approximation algorithm for the bandpass problem

Abstract

Publication series

Conference

Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this