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
N1 - Publisher Copyright:
© 2013, Springer Science+Business Media New York.
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 - http://www.scopus.com/inward/record.url?scp=84940718518&partnerID=8YFLogxK
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 -