{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T21:40:38Z","timestamp":1784238038965,"version":"3.55.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T00:00:00Z","timestamp":1624838400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T00:00:00Z","timestamp":1624838400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"UNKP-20-3 New National Excellence Program of the Ministry for Innovation and Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2021,10]]},"abstract":"Abstract<\/jats:title>This paper introduces the d<\/jats:italic>-distance matching problem<\/jats:italic>, in which we are given a bipartite graph $$G=(S,T;E)$$<\/jats:tex-math>\n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n S<\/mml:mi>\n ,<\/mml:mo>\n T<\/mml:mi>\n \u037e<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with $$S=\\{s_1,\\dots ,s_n\\}$$<\/jats:tex-math>\n \n S<\/mml:mi>\n =<\/mml:mo>\n {<\/mml:mo>\n \n s<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n \n s<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, a weight function on the edges and an integer $$d\\in \\mathbb Z_+$$<\/jats:tex-math>\n \n d<\/mml:mi>\n \u2208<\/mml:mo>\n \n Z<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The goal is to find a maximum-weight subset $$M\\subseteq E$$<\/jats:tex-math>\n \n M<\/mml:mi>\n \u2286<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the edges satisfying the following two conditions: (i) the degree of every node of S<\/jats:italic> is at most one in M<\/jats:italic>, (ii) if $$s_it,s_jt\\in M$$<\/jats:tex-math>\n \n \n s<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n t<\/mml:mi>\n ,<\/mml:mo>\n \n s<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n t<\/mml:mi>\n \u2208<\/mml:mo>\n M<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, then $$|j-i|\\ge d$$<\/jats:tex-math>\n \n |<\/mml:mo>\n j<\/mml:mi>\n -<\/mml:mo>\n i<\/mml:mi>\n |<\/mml:mo>\n \u2265<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. 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<\/jats:italic> and also show that the case when the size of T<\/jats:italic> 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}$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n -<\/mml:mo>\n \n 1<\/mml:mn>\n \n 2<\/mml:mn>\n d<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial $$(2-\\frac{1}{d})$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 2<\/mml:mn>\n -<\/mml:mo>\n \n 1<\/mml:mn>\n d<\/mml:mi>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-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 $$<\/jats:tex-math>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n +<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any constant $$\\epsilon >0$$<\/jats:tex-math>\n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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.<\/jats:p>","DOI":"10.1007\/s10479-021-04127-8","type":"journal-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T06:04:00Z","timestamp":1624860240000},"page":"137-161","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Matchings under distance constraints I."],"prefix":"10.1007","volume":"305","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4574-337X","authenticated-orcid":false,"given":"P\u00e9ter","family":"Madarasi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,28]]},"reference":[{"issue":"1","key":"4127_CR1","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"KI Aardal","year":"2007","unstructured":"Aardal, K. I., van Hoesel, S. P. M., Koster, A. M. C. A., Mannino, C., & Sassano, A. (2007). Models and solution techniques for frequency assignment problems. Annals of Operations Research, 153(1), 79\u2013129. https:\/\/doi.org\/10.1007\/s10479-007-0178-0.","journal-title":"Annals of Operations Research"},{"key":"4127_CR2","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.dam.2019.04.024","volume":"267","author":"J Baste","year":"2019","unstructured":"Baste, J., Rautenbach, D., & Sau, I. (2019). Approximating maximum uniquely restricted matchings in bipartite graphs. Discrete Applied Mathematics, 267, 30\u201340.","journal-title":"Discrete Applied Mathematics"},{"key":"4127_CR3","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-642-13036-6_4","volume-title":"Integer programming and combinatorial optimization","author":"K B\u00e9rczi","year":"2010","unstructured":"B\u00e9rczi, K., & V\u00e9gh, L. A. (2010). Restricted b-matchings in degree-bounded graphs. In F. Eisenbrand & F. B. Shepherd (Eds.), Integer programming and combinatorial optimization (pp. 43\u201356). Berlin: Springer."},{"key":"4127_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Parameterized complexity. Berlin: Springer Publishing Company."},{"key":"4127_CR5","volume-title":"Connections in combinatorial optimization","author":"A Frank","year":"2011","unstructured":"Frank, A. (2011). Connections in combinatorial optimization. Oxford: Oxford University Press."},{"issue":"1\u20132","key":"4127_CR6","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s10479-019-03311-1","volume":"279","author":"M F\u00fcrst","year":"2019","unstructured":"F\u00fcrst, M., & Rautenbach, D. (2019). On some hard and some tractable cases of the maximum acyclic matching problem. Annals of Operations Research, 279(1\u20132), 291\u2013300.","journal-title":"Annals of Operations Research"},{"key":"4127_CR7","volume-title":"Computers and intractability: A guide to the theory of NP-completeness (Series of books in the mathematical sciences), first edition","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness (Series of books in the mathematical sciences), first edition. W. H: Freeman."},{"key":"4127_CR8","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/322092.322093","volume":"25","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M., & Tanimoto, S. (1978). Some matching problems for bipartite graphs. Journal of the ACM, 25, 517\u2013525. https:\/\/doi.org\/10.1145\/322092.322093.","journal-title":"Journal of the ACM"},{"key":"4127_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R Karp","year":"1972","unstructured":"Karp, R. (1972). Reducibility among combinatorial problems. In R. Miller & J. Thatcher (Eds.), Complexity of computer computations (pp. 85\u2013103). New York: Plenum Press."},{"key":"4127_CR10","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-030-53262-8_17","volume-title":"Combinatorial optimization","author":"P Madarasi","year":"2020","unstructured":"Madarasi, P. (2020). The distance matching problem. In M. Ba\u00efou, B. Gendron, O. G\u00fcnl\u00fck, & A. R. Mahjoub (Eds.), Combinatorial optimization (pp. 202\u2013213). Cham: Springer International Publishing."},{"issue":"2","key":"4127_CR11","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/060652282","volume":"21","author":"M Makai","year":"2007","unstructured":"Makai, M. (2007). On maximum cost $$k_{t, t}$$-free $$t$$-matchings of bipartite graphs. SIAM Journal on Discrete Mathematics, 21(2), 349\u2013360. https:\/\/doi.org\/10.1137\/060652282.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4127_CR12","unstructured":"Pap, G.: Alternating paths revisited ii: Restricted b-matchings in bipartite graphs. EGRES Technical Report TR-2005-13 (2005)"},{"key":"4127_CR13","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"E Tardos","year":"1985","unstructured":"Tardos, E. (1985). A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5, 247\u2013255.","journal-title":"Combinatorica"},{"key":"4127_CR14","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1016\/S0165-1684(03)00089-6","volume":"83","author":"T Zeitlhofer","year":"2003","unstructured":"Zeitlhofer, T., & Wess, B. (2003). List-coloring of interval graphs with application to register assignment for heterogeneous register-set architectures. Signal Processing, 83, 1411\u20131425.","journal-title":"Signal Processing"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04127-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-04127-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04127-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T14:25:10Z","timestamp":1631629510000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-04127-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,28]]},"references-count":14,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["4127"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-04127-8","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,28]]},"assertion":[{"value":"15 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}