An Improved Approximation Algorithm for the Bandpass Problem

摘要

The general Bandpass-B problem is NP-hard and can be approximated by a reduction into the B-set packing problem, with a worst case performance ratio of O(B~2). When B = 2, a maximum weight matching gives a 2-approximation to the problem. The Bandpass-2 problem, or simply the Bandpass problem, can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present in this paper a 36/19-approximation algorithm for the Bandpass problem, which is the first improvement over the simple maximum weight matching based 2-approximation algorithm.