Matchings under distance constraints II

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

Annals of Operations Research, 2024, vol. 332, issue 1, No 13, 303-327

Abstract: Abstract This paper introduces the d-distance b-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, an integer $$d\in \mathbb {Z}_+$$ d ∈ Z + and a degree bound function $$b:S\cup T\rightarrow \mathbb {Z}_+$$ b : S ∪ T → Z + . The goal is to find a maximum-weight subset $$M\subseteq E$$ M ⊆ E of the edges satisfying the following two conditions: (1) the degree of each node $$v\in S\cup T$$ v ∈ S ∪ T is at most b(v) in M, (2) if $$s_it,s_jt\in M$$ s i t , s j t ∈ M , then $$|i-j|\ge d$$ | i - j | ≥ d . In the cyclic version of the problem, the nodes in S are considered to be in cyclic order. We get back the (cyclic) d-distance matching problem when $$b(s) = 1$$ b ( s ) = 1 for $$s\in S$$ s ∈ S and $$b(t) = \infty $$ b ( t ) = ∞ for $$t\in T$$ t ∈ T . We prove that the d-distance matching problem is APX-hard, even in the unweighted case. We show that $$2-\frac{1}{d}$$ 2 - 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)$$ ( 2 d - 1 ) divides the size of S. For the non-cyclic case, the integrality gap is shown to be at most $$(2-\frac{2}{d})$$ ( 2 - 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$$ b ≡ 2 or $$d=2$$ d = 2 , and we give e-approximation algorithms.

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

Downloads: (external link)
http://link.springer.com/10.1007/s10479-023-05703-w 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:332:y:2024:i:1:d:10.1007_s10479-023-05703-w

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

DOI: 10.1007/s10479-023-05703-w

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 ().