|
This paper introduces the \emph{$d$-distance $b$-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, an integer $d\in\Z_+$ and a degree bound function $b:S\cup T\to\Z_+$.
The goal is to find a maximum-weight subset $M\subseteq E$ of the edges satisfying the following two conditions: 1) the degree of each node $v\in S\cup T$ is at most $b(v)$ in $M$, 2) if $s_it,s_jt\in M$, then $|i-j|\geq d$.
In the cyclic version of the problem, the nodes in $S$ are considered to be in cyclic order.
We get back the \emph{(cyclic) $d$-distance matching problem} when $b(s) = 1$ for $s\in S$ and $b(t) = \infty$ for $t\in T$.
We prove that the $d$-distance matching problem is APX-hard, even in the unweighted case.
We show that $(2-\frac{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 $(2d-1)$ divides the size of $S$.
For the non-cyclic case, the integrality gap is shown to be at most $(2-\frac{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\equiv 2$ or $d=2$, and we give $e$-approximation algorithms.
Bibtex entry:
| AUTHOR | = | {Madarasi, P{\'e}ter}, |
| TITLE | = | {Matchings under distance constraints II.}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2023}, |
| NUMBER | = | {TR-2023-10} |