Matchings under distance constraints I

This paper introduces the d-distance matching problem, in which we are given a bipartite graph $$G=(S,T;E)$$ G = ( S , T ; E ) with $$S=\{s_1,\dots ,s_n\}$$ S = { s 1 , ⋯ , s n } , a weight function on the edges and an integer $$d\in \mathbb Z_+$$ d ∈ Z + . The goal is to find a maximum-weight subset $$M\subseteq E$$ M ⊆ E of the edges satisfying the following two conditions: (i) the degree of every node of S is at most one in M, (ii) if $$s_it,s_jt\in M$$ s i t , s j t ∈ M , then $$|j-i|\ge d$$ | j - i | ≥ d . This question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple 3-approximation. We give an FPT algorithm parameterized by d and also show that the case when the size of T is constant can be solved in polynomial time. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most $$2-\frac{1}{2d-1}$$ 2 - 1 2 d - 1 , and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial $$(2-\frac{1}{d})$$ ( 2 - 1 d ) -approximation algorithm is also presented. Several greedy approaches are considered, and a local search algorithm is described that achieves an approximation ratio of $$3/2+\epsilon $$ 3 / 2 + ϵ for any constant $$\epsilon >0$$ ϵ > 0 in the unweighted case. The novel approaches used in the analysis of the integrality gap and the approximation ratio of locally optimal solutions might be of independent combinatorial interest.