Matchings under distance constraints I

Péter Madarasi ()
Additional contact information
Péter Madarasi: Eötvös Loránd University

Annals of Operations Research, 2021, vol. 305, issue 1, No 6, 137-161

Abstract: Abstract 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.

Keywords: Distance matching; Restricted b-matching; Constrained matching; Scheduling; Parameterized algorithms; Approximation algorithms; Integrality gap (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04127-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:305:y:2021:i:1:d:10.1007_s10479-021-04127-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04127-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().