The distance matching problem

DOI10.1007/978-3-030-53262-8_17MaRDI QIDQ2225064zbMATH OpenOpenAlexFDO

Authors Péter Madarasi

Publication date 4 February 2021

Full work available at URL https://arxiv.org/abs/1911.12432

zbMATH Keywords

approximation algorithmsdistance matchingintegrality gapparameterized algorithmsrestricted matchingshift scheduling

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: 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 $dinmathbb{Z}_{+}$. The goal is to find a maximum weight subset $MsubseteqE$ 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_{i}t,s_{j}tinM$, then $|j-i|geqd$. The question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple $3$-approxi-mation. We give an FPT algorithm parameterized by $d$ and also settle the case when the size of $T$ is constant. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most $2-frac12d-1$, and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial $(2-frac1d)$-approximation algorithm is also presented. Several greedy approaches are considered, in particular, a local search algorithm 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.

Recommendations

• The Euclidean Matching Problem
• An Optimal Matching Problem for the Euclidean Distance
• The Erdős distance problem
• The Metric Nearness Problem
• On the approximate unit distance problem
• The distance orientation problem
• scientific article; zbMATH DE number 5031986
• Distance on matchings: An axiomatic approach

Cited in

(8)

• The distance orientation problem
• Matchings under distance constraints. I
• On Romeo and Juliet problems: minimizing distance-to-sight
• The Euclidean Matching Problem
• An Optimal Matching Problem for the Euclidean Distance
• scientific article; zbMATH DE number 5031986 (Why is no real title available?)
• Matching with sizes (or scheduling with processing set restrictions)
• Matchings under distance constraints. II.

This page was built for publication: The distance matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225064)