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 | |
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