|
Abstract: |
The general Bandpass-B problem is NP-hard and can be approximated by a reduction into the weighted 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. In this talk, we call the Bandpass-2 problem simply the Bandpass problem. 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 a 426/227-approximation algorithm for the problem. Such an improved approximation is built on an intrinsic structural property proven for the optimal solution and several novel schemes to partition a b-matching into desired matchings. |
