A 0.5358-approximation for Bandpass-2

Liqin Huang; Weitian Tong; Randy Goebel; Tian Liu; Guohui Lin

doi:10.1007/s10878-013-9656-2

A 0.5358-approximation for Bandpass-2

Liqin Huang, Weitian Tong, Randy Goebel, Tian Liu, Guohui Lin

Computer Science

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

The Bandpass-2 problem is a variant of the maximum traveling salesman problem arising from optical communication networks using wavelength-division multiplexing technology, in which the edge weights are dynamic rather than fixed. The previously best approximation algorithm for this NP-hard problem has a worst-case performance ratio of 227426. Here we present a novel scheme to partition the edge set of a 4-matching into a number of subsets, such that the union of each of them and a given matching is an acyclic 2-matching. Such a partition result takes advantage of a known structural property of the optimal solution, leading to a 70-2128≈0.5358-approximation algorithm for the Bandpass-2 problem.

Original language	English
Pages (from-to)	612-626
Number of pages	15
Journal	Journal of Combinatorial Optimization
Volume	30
Issue number	3
DOIs	https://doi.org/10.1007/s10878-013-9656-2
State	Published - Oct 1 2015

Scopus Subject Areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Keywords

Acyclic 2-matching
Approximation algorithm
Maximum weight b-matching
The Bandpass problem
Worst case performance ratio

Access to Document

10.1007/s10878-013-9656-2

Cite this

@article{2800baf4fa7e459a9bcb154f1a556548,

title = "A 0.5358-approximation for Bandpass-2",

abstract = "The Bandpass-2 problem is a variant of the maximum traveling salesman problem arising from optical communication networks using wavelength-division multiplexing technology, in which the edge weights are dynamic rather than fixed. The previously best approximation algorithm for this NP-hard problem has a worst-case performance ratio of 227426. Here we present a novel scheme to partition the edge set of a 4-matching into a number of subsets, such that the union of each of them and a given matching is an acyclic 2-matching. Such a partition result takes advantage of a known structural property of the optimal solution, leading to a 70-2128≈0.5358-approximation algorithm for the Bandpass-2 problem.",

keywords = "Acyclic 2-matching, Approximation algorithm, Maximum weight b-matching, The Bandpass problem, Worst case performance ratio",

author = "Liqin Huang and Weitian Tong and Randy Goebel and Tian Liu and Guohui Lin",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Science+Business Media New York.",

year = "2015",

month = oct,

day = "1",

doi = "10.1007/s10878-013-9656-2",

language = "English",

volume = "30",

pages = "612--626",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - A 0.5358-approximation for Bandpass-2

AU - Huang, Liqin

AU - Tong, Weitian

AU - Goebel, Randy

AU - Liu, Tian

AU - Lin, Guohui

PY - 2015/10/1

Y1 - 2015/10/1

N2 - The Bandpass-2 problem is a variant of the maximum traveling salesman problem arising from optical communication networks using wavelength-division multiplexing technology, in which the edge weights are dynamic rather than fixed. The previously best approximation algorithm for this NP-hard problem has a worst-case performance ratio of 227426. Here we present a novel scheme to partition the edge set of a 4-matching into a number of subsets, such that the union of each of them and a given matching is an acyclic 2-matching. Such a partition result takes advantage of a known structural property of the optimal solution, leading to a 70-2128≈0.5358-approximation algorithm for the Bandpass-2 problem.

AB - The Bandpass-2 problem is a variant of the maximum traveling salesman problem arising from optical communication networks using wavelength-division multiplexing technology, in which the edge weights are dynamic rather than fixed. The previously best approximation algorithm for this NP-hard problem has a worst-case performance ratio of 227426. Here we present a novel scheme to partition the edge set of a 4-matching into a number of subsets, such that the union of each of them and a given matching is an acyclic 2-matching. Such a partition result takes advantage of a known structural property of the optimal solution, leading to a 70-2128≈0.5358-approximation algorithm for the Bandpass-2 problem.

KW - Acyclic 2-matching

KW - Approximation algorithm

KW - Maximum weight b-matching

KW - The Bandpass problem

KW - Worst case performance ratio

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

U2 - 10.1007/s10878-013-9656-2

DO - 10.1007/s10878-013-9656-2

M3 - Article

AN - SCOPUS:84940718518

SN - 1382-6905

VL - 30

SP - 612

EP - 626

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

A 0.5358-approximation for Bandpass-2

Abstract

Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this