{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T04:08:37Z","timestamp":1769832517927,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,8,21]],"date-time":"2022-08-21T00:00:00Z","timestamp":1661040000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,21]],"date-time":"2022-08-21T00:00:00Z","timestamp":1661040000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universidad de Cadiz"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we deal with minimum cost <jats:italic>b<\/jats:italic>-matching problems on graphs where the nodes are assumed to belong to non-necessarily convex regions called neighborhoods, and the costs are given by the distances between points of the neighborhoods. The goal in the proposed problems is twofold: (i) finding a <jats:italic>b<\/jats:italic>-matching in the graph and (ii) determining a point in each neighborhood to be the connection point among the edges defining the b-matching. Different variants of the minimum cost <jats:italic>b<\/jats:italic>-matching problem are considered depending on the criteria to match neighborhoods: perfect, maximum cardinality, maximal and the <jats:italic>a<\/jats:italic>\u2013<jats:italic>b<\/jats:italic>-matching problems. The theoretical complexity of solving each one of these problems is analyzed. Different mixed integer non-linear programming formulations are proposed for each one of the considered problems and then reformulated as Second Order Cone formulations. An extensive computational experience shows the efficiency of the proposed formulations to solve the problems under study.<\/jats:p>","DOI":"10.1007\/s10589-022-00406-7","type":"journal-article","created":{"date-parts":[[2022,8,21]],"date-time":"2022-08-21T02:02:41Z","timestamp":1661047361000},"page":"525-553","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Minimum cost b-matching problems with neighborhoods"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8905-7825","authenticated-orcid":false,"given":"I.","family":"Espejo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"P\u00e1ez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Puerto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. M.","family":"Rodr\u00edguez-Ch\u00eda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,21]]},"reference":[{"key":"406_CR1","first-page":"351","volume-title":"COCOA 2013. Lecture Notes in Computer Science","author":"A Ahadi","year":"2013","unstructured":"Ahadi, A., Mozafari, A., Zarei, A.: Touring disjoint polygons problem is NP-hard. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. Lecture Notes in Computer Science, vol. 8287, pp. 351\u2013360. Springer, Cham (2013)"},{"key":"406_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(87)90178-5","volume":"24","author":"RP Anstee","year":"1987","unstructured":"Anstee, R.P.: A polynomial algorithm for $$b$$-matchings, an alternative approach. Inf. Process. Lett. 24, 153\u2013157 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"406_CR3","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"EM Arkin","year":"1994","unstructured":"Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3), 197\u2013218 (1994)","journal-title":"Discrete Appl. Math."},{"key":"406_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0167-5060(08)70342-X","volume":"5","author":"E Balas","year":"1979","unstructured":"Balas, E.: Disjunctive programming. Ann. Discrete Math. 5, 3\u201351 (1979)","journal-title":"Ann. Discrete Math."},{"key":"406_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization. In: Analysis, algorithms and engineering applications. SIAM Series (2001)","DOI":"10.1137\/1.9780898718829"},{"key":"406_CR6","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/s10589-019-00077-x","volume":"73","author":"V Blanco","year":"2019","unstructured":"Blanco, V.: Ordered p-median problems with neighborhoods. Comput. Optim. Appl. 73, 603\u2013645 (2019)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"406_CR7","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10589-014-9638-z","volume":"58","author":"V Blanco","year":"2014","unstructured":"Blanco, V., Puerto, J., El-Haj Ben-Ali, S.: Revisiting several problems and algorithms in continuous location with $$\\ell _\\tau$$ norms. Comput. Optim. Appl. 58(3), 563\u2013595 (2014)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"406_CR8","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1016\/j.ejor.2017.04.023","volume":"262","author":"V Blanco","year":"2017","unstructured":"Blanco, V., Fern\u00e1ndez, E., Puerto, J.: Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods. Eur. J. Oper. Res. 262(3), 863\u2013878 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"406_CR9","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1002\/net.21516","volume":"62","author":"M Bodur","year":"2013","unstructured":"Bodur, M., Ekim, T., Taskin, Z.C.: Decomposition algorithms for solving the minimum weight maximal matching problem. Networks 62, 273\u2013287 (2013)","journal-title":"Networks"},{"key":"406_CR10","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Madry, A., Sankowski, P., Vladu, A.: Negative-weight shortest paths and unit capacity minimum cost flow in $$\\cal{O}(m^{10\/7} log W)$$ Time. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 752\u2013771 (2017)","DOI":"10.1137\/1.9781611974782.48"},{"key":"406_CR11","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/BFb0121194","volume-title":"Polyhedral Combinatorics. Mathematical Programming Studies","author":"WH Cunningham","year":"1978","unstructured":"Cunningham, W.H., Marsh, A.B.: A primal algorithm for optimum matching. In: Balinski, M.L., Hoffman, A.J. (eds.) Polyhedral Combinatorics. Mathematical Programming Studies, vol. 8, pp. 50\u201372. Springer, Berlin, Heidelberg (1978)"},{"issue":"1","key":"406_CR12","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.jalgor.2005.01.010","volume":"57","author":"M De Berg","year":"2005","unstructured":"De Berg, M., Gudmundsson, J., Katz, M.J., Levcopoulus, C., Overmars, M.H., Van der Stappen, A.F.: TSP with neighborhoods of varying size. J. Algorithms 57(1), 22\u201336 (2005)","journal-title":"J. Algorithms"},{"key":"406_CR13","doi-asserted-by":"publisher","first-page":"116618","DOI":"10.1016\/j.energy.2019.116618","volume":"192","author":"L Dong","year":"2020","unstructured":"Dong, L., Kang, X., Pan, M., Zhao, M., Zhang, F., Yao, H.: B-matching-based optimization model for energy allocation in sea surface monitoring. Energy 192, 116618 (2020)","journal-title":"Energy"},{"issue":"1","key":"406_CR14","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/s00224-014-9591-3","volume":"56","author":"R Dorrigiv","year":"2015","unstructured":"Dorrigiv, R., Fraser, R., He, M., Kamali, S., Kawamura, A., L\u00f3pez-Ortiz, A., Seco, D.: On minimum-and maximum-weight minimum spanning trees with neighborhoods. Theory Comput. Syst. 56(1), 220\u2013250 (2015)","journal-title":"Theory Comput. Syst."},{"key":"406_CR15","doi-asserted-by":"crossref","unstructured":"Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 473\u2013482 (2003)","DOI":"10.1145\/780542.780612"},{"issue":"1","key":"406_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0196-6774(03)00047-6","volume":"48","author":"A Dumitrescu","year":"2003","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms 48(1), 135\u2013159 (2003)","journal-title":"J. Algorithms"},{"issue":"3","key":"406_CR17","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"406_CR18","first-page":"189","volume-title":"Theory and Practice of Computer Science. SOFEM 2021. Lecture Notes in Computer Science","author":"Y Emek","year":"2021","unstructured":"Emek, Y., Kutten, S., Shalom, M., Zaks, S.: Hierarchical b-Matching. In: Bure\u0161, T., et al. (eds.) Theory and Practice of Computer Science. SOFEM 2021. Lecture Notes in Computer Science, vol. 12607, pp. 189\u2013202. Springer, Cham (2021)"},{"issue":"3","key":"406_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3183369","volume":"14","author":"HN Gabow","year":"2018","unstructured":"Gabow, H.N.: Data structures for weighted matching and extensions to $$b$$-matching and $$f$$-factors. ACM Trans. Algorithms (TALG) 14(3), 1\u201380 (2018)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"2","key":"406_CR20","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1080\/10556788.2011.648932","volume":"28","author":"I Gentilini","year":"2013","unstructured":"Gentilini, I., Margot, F., Shimada, K.: The travelling salesman problem with neighbourhoods: MINLP solution. Optim. Methods Softw. 28(2), 364\u2013378 (2013)","journal-title":"Optim. Methods Softw."},{"key":"406_CR21","first-page":"135","volume-title":"Handbooks in Operations Research and Management Science. Network Models","author":"AMH Gerards","year":"1995","unstructured":"Gerards, A.M.H.: Matching. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Handbooks in Operations Research and Management Science. Network Models, vol. 7, pp. 135\u2013224. Elsevier, North-Holland (1995)"},{"issue":"4","key":"406_CR22","first-page":"473","volume":"6","author":"J Gudmundsson","year":"1999","unstructured":"Gudmundsson, J., Levcopoulos, C.: A fast approximation algorithm for TSP with neighborhoods. Nord. J. Comput. 6(4), 473\u2013482 (1999)","journal-title":"Nord. J. Comput."},{"key":"406_CR23","unstructured":"Gurobi Optimization Inc. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com (2021) Accessed 7 November 2021"},{"key":"406_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56252-0","volume-title":"Matching Theory for Wireless Networks. Wireless Networks Series","author":"Z Han","year":"2017","unstructured":"Han, Z., Gu, Y., Saad, W.: Matching Theory for Wireless Networks. Wireless Networks Series. Springer, Cham (2017)"},{"key":"406_CR25","unstructured":"Lovasz, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics, vol. 29. North Holland (1986)"},{"key":"406_CR26","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0024-3795(98)10032-0","volume":"284","author":"M Lobo","year":"1998","unstructured":"Lobo, M., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193\u2013228 (1998)","journal-title":"Linear Algebra Appl."},{"key":"406_CR27","doi-asserted-by":"crossref","unstructured":"Luemberger, D.G., Ye, Y.: Linear and Nonlinear Programming. International Series in Operations Research and Management Science. Springer, New York (2008)","DOI":"10.1007\/978-0-387-74503-9"},{"issue":"3","key":"406_CR28","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0220026","volume":"20","author":"O Marcotte","year":"1991","unstructured":"Marcotte, O., Suri, S.: Fast matching algorithms for points on a polygon. SIAM J. Comput. 20(3), 405\u2013422 (1991)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"406_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/ijoc.7.1.1","volume":"7","author":"DL Miller","year":"1995","unstructured":"Miller, D.L.: A matching based exact algorithm for capacitated vehicle routing problems. ORSA J. Comput. 7(1), 1\u20139 (1995)","journal-title":"ORSA J. Comput."},{"key":"406_CR30","unstructured":"Millman National Land Services: What Is a Cell Tower and How Does a Cell Tower Work? https:\/\/millmanland.com\/company-news\/what-is-a-cell-tower-and-how-does-a-cell-tower-work (2021). Accessed 7 November 2021"},{"key":"406_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.06.061","author":"J Puerto","year":"2021","unstructured":"Puerto, J., Valverde, C.: Routing for unmanned aerial vehicles, touring dimensional sets. Eur. J. Oper. Res. (2021). https:\/\/doi.org\/10.1016\/j.ejor.2021.06.061","journal-title":"Eur. J. Oper. Res."},{"key":"406_CR32","first-page":"179","volume-title":"Handbook of Combinatorics","author":"WR Pulleyblank","year":"1995","unstructured":"Pulleyblank, W.R.: Matchings and extensions. In: Graham, R.L., Gr\u00f6tschel, M., Lov\u00e1sz, L. (eds.) Handbook of Combinatorics, vol. 1, pp. 179\u2013232. Elsevier, Amsterdam (1995)"},{"key":"406_CR33","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s10589-006-9003-y","volume":"36","author":"O Schenk","year":"2007","unstructured":"Schenk, O., W\u00e4chter, A., Hagemann, M.: Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization. Comput. Optim. Appl. 36, 321\u2013341 (2007)","journal-title":"Comput. Optim. Appl."},{"key":"406_CR34","doi-asserted-by":"crossref","unstructured":"Sherali, H.D., Shetty, C.M.: Optimization with disjunctive constraints. Lecture Notes in Economics and Mathematical Systems, vol. 181. Springer, Heidelberg (1980)","DOI":"10.1007\/978-3-642-48794-1"},{"key":"406_CR35","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1007\/s11590-011-0351-x","volume":"6","author":"ZC Ta\u015fkin","year":"2012","unstructured":"Ta\u015fkin, Z.C., Ekim, T.: Integer programming formulations for the minimum weighted maximal matching problem. Optim. Lett. 6, 1161\u20131171 (2012)","journal-title":"Optim. Lett."},{"issue":"1\u20132","key":"406_CR36","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0004-3702(02)00229-1","volume":"140","author":"M Tennenholtz","year":"2002","unstructured":"Tennenholtz, M.: Tractable combinatorial auctions and b-matching. Artif. Intell. 140(1\u20132), 231\u2013243 (2002)","journal-title":"Artif. Intell."},{"issue":"3","key":"406_CR37","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1080\/10556788.2015.1104679","volume":"31","author":"MK Tural","year":"2016","unstructured":"Tural, M.K.: Maximal matching polytope in trees. Optim. Method. Softw. 31(3), 471\u2013478 (2016)","journal-title":"Optim. Method. Softw."},{"key":"406_CR38","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"PM Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Geometry helps in matching. SIAM J. Comput. 18, 1201\u20131225 (1989)","journal-title":"SIAM J. Comput."},{"key":"406_CR39","volume-title":"Algorithmic Aspects in Information and Management. AAIM 2007. Lecture Notes in Computer Science","author":"Y Yang","year":"2007","unstructured":"Yang, Y., Lin, M., Xu, J., Xie, Y.: Minimum spanning tree with neighborhoods. In: Kao, M.Y., Li, X.Y. (eds.) Algorithmic Aspects in Information and Management. AAIM 2007. Lecture Notes in Computer Science, vol. 4508. Springer, Berlin (2007)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00406-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-022-00406-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00406-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T12:19:32Z","timestamp":1664453972000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-022-00406-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,21]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["406"],"URL":"https:\/\/doi.org\/10.1007\/s10589-022-00406-7","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,21]]},"assertion":[{"value":"10 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interests"}}]}}