|
This paper introduces the \emph{$d$-distance matching problem}, in which we are given a bipartite graph $G=(S,T;E)$ with $S=\{s_1,\dots,s_n\}$,
a weight function on the edges and an integer $d\in\Z_+$. The goal is to find a maximum-weight subset $M\subseteq 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$, then $|j-i|\geq 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}$, and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial $(2-\frac{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$ for any constant $\epsilon>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.
Bibtex entry:
| AUTHOR | = | {Madarasi, P{\'e}ter}, |
| TITLE | = | {Matchings under distance constraints I.}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2021}, |
| NUMBER | = | {TR-2021-02} |