Indexed by:
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. © 2013, Springer Science+Business Media New York.
Keyword:
Reprint 's Address:
Email:
Source :
Journal of Combinatorial Optimization
ISSN: 1382-6905
Year: 2015
Issue: 3
Volume: 30
Page: 612-626
1 . 0 8
JCR@2015
0 . 9 0 0
JCR@2023
ESI HC Threshold:86
JCR Journal Grade:2
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: