Matchings under distance constraints II.

This paper introduces the d-distanceb-matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges, an integer d ∈ Z + and a degree bound function b : S ∪ T → Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (1) the degree of each node v ∈ S ∪ T is at most b(v) in M, (2) if s i t , s j t ∈ M , then | i - j | ≥ d . In the cyclic version of the problem, the nodes in S are considered to be in cyclic order. We get back the (cyclic)d-distance matching problem when b (s) = 1 for s ∈ S and b (t) = ∞ for t ∈ T . We prove that the d-distance matching problem is APX-hard, even in the unweighted case. We show that 2 - 1 d is a tight upper bound on the integrality gap of the natural integer programming model for the cyclic d-distance b-matching problem provided that (2 d - 1) divides the size of S. For the non-cyclic case, the integrality gap is shown to be at most (2 - 2 d) . The proofs give approximation algorithms with guarantees matching these bounds, and also improve the best known algorithms for the (cyclic) d-distance matching problem. In a related problem, our goal is to find a permutation of S maximizing the weight of the optimal d-distance b-matching. This problem can be solved in polynomial time for the (cyclic) d-distance matching problem — even though the (cyclic) d-distance matching problem itself is NP-hard and also hard to approximate arbitrarily. For (cyclic) d-distance b-matchings, however, we prove that finding the best permutation is NP-hard, even if b ≡ 2 or d = 2 , and we give e-approximation algorithms. [ABSTRACT FROM AUTHOR]