{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:07Z","timestamp":1740145147370,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2024,1,26]],"date-time":"2024-01-26T00:00:00Z","timestamp":1706227200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,26]],"date-time":"2024-01-26T00:00:00Z","timestamp":1706227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018694","name":"HORIZON EUROPE Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["#734922"],"award-info":[{"award-number":["#734922"]}],"id":[{"id":"10.13039\/100018694","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["CIN\/AEI\/10.13039\/501100011033 (PID2020-114154RB-I00)"],"award-info":[{"award-number":["CIN\/AEI\/10.13039\/501100011033 (PID2020-114154RB-I00)"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013395","name":"Sistema Nacional de Investigadores","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013395","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005739","name":"Universidad Nacional Aut\u00f3noma de M\u00e9xico","doi-asserted-by":"publisher","award":["#734922"],"award-info":[{"award-number":["#734922"]}],"id":[{"id":"10.13039\/501100005739","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009042","name":"Universidad de Sevilla","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009042","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the minimum-weight many-to-many point matching problem, we are given a set <jats:italic>R<\/jats:italic> of red points and a set <jats:italic>B<\/jats:italic> of blue points in the plane, of total size <jats:italic>N<\/jats:italic>, and we want to pair up each point in <jats:italic>R<\/jats:italic> to one or more points in <jats:italic>B<\/jats:italic> and vice versa so that the sum of distances between the paired points is minimized. This problem can be solved in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(N^3)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>N<\/mml:mi>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time by using a reduction to the minimum-weight perfect matching problem, and thus, it is not fast enough to be used for on-line systems where a large number of tunes need to be compared. Motivated by similarity problems in music theory, in this paper we study several constrained minimum-weight many-to-many point matching problems in which the allowed pairings are given by geometric restrictions, i.e., a bichromatic pair can be matched if and only if the corresponding points satisfy a specific condition of closeness. We provide algorithms to solve these constrained versions in <jats:italic>O<\/jats:italic>(<jats:italic>N<\/jats:italic>) time when the sets <jats:italic>R<\/jats:italic> and <jats:italic>B<\/jats:italic> are given ordered by abscissa.<\/jats:p>","DOI":"10.1007\/s11590-023-02089-3","type":"journal-article","created":{"date-parts":[[2024,1,26]],"date-time":"2024-01-26T11:02:19Z","timestamp":1706266939000},"page":"1837-1854","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Constrained many-to-many point matching in two dimensions"],"prefix":"10.1007","volume":"18","author":[{"given":"L. E.","family":"Caraballo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. A.","family":"Castro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. M.","family":"D\u00edaz-B\u00e1\u00f1ez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. A.","family":"Heredia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1217-3913","authenticated-orcid":false,"given":"I.","family":"Ventura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. J.","family":"Zaragoza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,26]]},"reference":[{"issue":"2","key":"2089_CR1","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0306-4573(01)00033-4","volume":"38","author":"D Byrd","year":"2002","unstructured":"Byrd, D., Crawford, T.: Problems of music information retrieval in the real world. Inf. Process. Manag. 38(2), 249\u2013272 (2002)","journal-title":"Inf. Process. Manag."},{"issue":"4","key":"2089_CR2","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1016\/j.sigpro.2009.06.020","volume":"90","author":"O Cornelis","year":"2010","unstructured":"Cornelis, O., Lesaffre, M., Moelants, D., Leman, M.: Access to ethnic music: advances and perspectives in content-based music information retrieval. Signal Process. 90(4), 1008\u20131031 (2010)","journal-title":"Signal Process."},{"issue":"2","key":"2089_CR3","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1080\/09298215.2016.1174717","volume":"45","author":"J Mora","year":"2016","unstructured":"Mora, J., G\u00f3mez, F., G\u00f3mez, E., D\u00edaz-B\u00e1\u00f1ez, J.M.: Melodic contour and mid-level global features applied to the analysis of flamenco cantes. J. New Music Res. 45(2), 145\u2013159 (2016)","journal-title":"J. New Music Res."},{"key":"2089_CR4","unstructured":"Clifford, R., Christodoulakis, M., Crawford, T., Meredith, D., Wiggins, G.A.: A fast, randomised, maximal subset matching algorithm for document-level music retrieval. In: ISMIR 2006, 7th International Conference on Music Information Retrieval, Victoria, Canada, 8\u201312 October 2006, Proceedings, pp. 150\u2013155 (2006)"},{"key":"2089_CR5","unstructured":"Gudmundsson, J., Klein, O., Knauer, C., Smid, M.: Small Manhattan networks and algorithmic applications for the earth mover\u2019s distance. In: Proceedings of the 23rd European Workshop on Computational Geometry, pp. 174\u2013177 (2007)"},{"issue":"8","key":"2089_CR6","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1002\/int.21735","volume":"30","author":"W Wang","year":"2015","unstructured":"Wang, W., Zhang, G., Lu, J.: Collaborative filtering with entropy-driven user similarity in recommender systems. Int. J. Intell. Syst. 30(8), 854\u2013870 (2015). https:\/\/doi.org\/10.1002\/int.21735","journal-title":"Int. J. Intell. Syst."},{"key":"2089_CR7","doi-asserted-by":"crossref","unstructured":"Mokbel, B., Hasenfuss, A., Hammer, B.: Graph-based representation of symbolic musical data. In: Graph-Based Representations in Pattern Recognition: 7th IAPR-TC-15 International Workshop, GbRPR 2009, Venice, Italy, May 26\u201328, 2009. Proceedings 7, pp. 42\u201351. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-02124-4_5"},{"issue":"4","key":"2089_CR8","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/j.ipl.2005.05.007","volume":"95","author":"J Colannino","year":"2005","unstructured":"Colannino, J., Toussaint, G.: An algorithm for computing the restriction scaffold assignment problem in computational biology. Inf. Process. Lett. 95(4), 466\u2013471 (2005). https:\/\/doi.org\/10.1016\/j.ipl.2005.05.007","journal-title":"Inf. Process. Lett."},{"issue":"3\u20134","key":"2089_CR9","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1089\/10665270360688084","volume":"10","author":"A Ben-Dor","year":"2003","unstructured":"Ben-Dor, A., Karp, R., Schwikowski, B., Shamir, R.: The restriction scaffold problem. J. Comput.Biol. J. Comput. Mol. Cell Biol. 10(3\u20134), 385\u2013398 (2003). https:\/\/doi.org\/10.1089\/10665270360688084","journal-title":"J. Comput.Biol. J. Comput. Mol. Cell Biol."},{"key":"2089_CR10","doi-asserted-by":"publisher","unstructured":"Toussaint, G.: The geometry of musical rhythm. In: Akiyama, J., Kano, M., Tan, X. (eds.) Discrete and Computational Geometry, pp. 198\u2013212. Springer, Berlin (2005). https:\/\/doi.org\/10.1007\/11589440_20","DOI":"10.1007\/11589440_20"},{"key":"2089_CR11","unstructured":"Toussaint, G.T.: A comparison of rhythmic similarity measures. In: Proceedings of Fifth International Conference on Music Information Retrieval, Barcelona, Spain, 10\u201315 October, pp. 242\u2013245 (2004)"},{"key":"2089_CR12","doi-asserted-by":"publisher","unstructured":"Typke, R., Wiering, F., Veltkamp, R.C.: Transportation distances and human perception of melodic similarity. Musicae Scientiae 11(1_suppl), 153\u2013181 (2007). https:\/\/doi.org\/10.1177\/102986490701100107","DOI":"10.1177\/102986490701100107"},{"issue":"2","key":"2089_CR13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s002360050075","volume":"34","author":"T Eiter","year":"1997","unstructured":"Eiter, T., Mannila, H.: Distance measures for point sets and their computation. Acta Informatica 34(2), 109\u2013133 (1997). https:\/\/doi.org\/10.1007\/s002360050075","journal-title":"Acta Informatica"},{"issue":"1\u20132","key":"2089_CR14","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Q. 2(1\u20132), 83\u201397 (1955). https:\/\/doi.org\/10.1002\/nav.3800020109","journal-title":"Naval Res. Logist. Q."},{"issue":"1","key":"2089_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s00373-007-0714-3","volume":"23","author":"J Colannino","year":"2007","unstructured":"Colannino, J., Damian, M., Hurtado, F., Langerman, S., Meijer, H., Ramaswami, S., Souvaine, D., Toussaint, G.: Efficient many-to-many point matching in one dimension. Graphs Comb. 23(1), 169\u2013178 (2007). https:\/\/doi.org\/10.1007\/s00373-007-0714-3","journal-title":"Graphs Comb."},{"key":"2089_CR16","doi-asserted-by":"publisher","unstructured":"Bandyapadhyay, S., Maheshwari, A., Smid, M.: Exact and approximation algorithms for many-to-many point matching in the plane. In: Ahn, H.-K., Sadakane, K. (eds.) 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 212, pp. 44\u201314414. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.44","DOI":"10.4230\/LIPIcs.ISAAC.2021.44"},{"issue":"2","key":"2089_CR17","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.ipl.2008.09.014","volume":"19","author":"H-J Lin","year":"2008","unstructured":"Lin, H.-J., Wu, H.-H., Kao, Y.-T.: Geometric measures of distance between two pitch contour sequences. J. Comput. 19(2), 44\u201366 (2008). https:\/\/doi.org\/10.1016\/j.ipl.2008.09.014","journal-title":"J. Comput."},{"key":"2089_CR18","unstructured":"Di\u00a0Lorenzo, P., Di\u00a0Maio, G.: The Hausdorff metric in the melody space: a new approach to melodic similarity. In: The 9th International Conference on Music Perception and Cognition, Alma Mater Studiorum University of Bologna, pp. 22\u201326 (2006)"},{"key":"2089_CR19","unstructured":"Kroher, N., G\u00f3mez, E., Guastavino, C., G\u00f3mez, F., Bonada, J.: Computational models for perceived melodic similarity in a cappella flamenco singing. In: ISMIR, pp. 65\u201370 (2014). Citeseer"},{"issue":"4","key":"2089_CR20","doi-asserted-by":"publisher","first-page":"2418","DOI":"10.1121\/1.5097588","volume":"145","author":"KK Ganguli","year":"2019","unstructured":"Ganguli, K.K., Rao, P.: On the perception of raga motifs by trained musicians. J. Acoust. Soc. Am. 145(4), 2418\u20132434 (2019)","journal-title":"J. Acoust. Soc. Am."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02089-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-023-02089-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02089-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T09:12:57Z","timestamp":1728119577000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-023-02089-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,26]]},"references-count":20,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["2089"],"URL":"https:\/\/doi.org\/10.1007\/s11590-023-02089-3","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2024,1,26]]},"assertion":[{"value":"10 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}