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

Fuzhou University
University of Alberta
Key Laboratory of High Confidence Software Technologies, Ministry of Education, Institute of Software, School of Electronic Engineering and Computer Science, Peking University

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