{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T22:57:56Z","timestamp":1774393076138,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,5,1]],"date-time":"2023-05-01T00:00:00Z","timestamp":1682899200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,1]],"date-time":"2023-05-01T00:00:00Z","timestamp":1682899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071417"],"award-info":[{"award-number":["12071417"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,5]]},"DOI":"10.1007\/s10878-023-01036-3","type":"journal-article","created":{"date-parts":[[2023,5,7]],"date-time":"2023-05-07T17:01:15Z","timestamp":1683478875000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Online bottleneck matching on a line"],"prefix":"10.1007","volume":"45","author":[{"given":"Man","family":"Xiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shu","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3094-4347","authenticated-orcid":false,"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinhua","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,7]]},"reference":[{"key":"1036_CR1","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/j.tcs.2019.08.011","volume":"806","author":"AR Ahmed","year":"2020","unstructured":"Ahmed AR, Rahman MS, Kobourov S (2020) Online facility assignment. Theor Comput Sci 806:455\u2013467","journal-title":"Theor Comput Sci"},{"issue":"1","key":"1036_CR2","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/s10878-012-9581-9","volume":"27","author":"BM Anthony","year":"2014","unstructured":"Anthony BM, Chung C (2014) Online bottleneck matching. J Comb Optim 27(1):100\u2013114","journal-title":"J Comb Optim"},{"issue":"4","key":"1036_CR3","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1007\/s10878-015-9948-9","volume":"32","author":"BM Anthony","year":"2016","unstructured":"Anthony BM, Chung C (2016) Serve or skip: the power of rejection in online bottleneck matching. J Comb Optim 32(4):1232\u20131253","journal-title":"J Comb Optim"},{"key":"1036_CR4","doi-asserted-by":"publisher","first-page":"2917","DOI":"10.1007\/s00453-019-00565-w","volume":"81","author":"A Antoniadis","year":"2019","unstructured":"Antoniadis A, Barcelo N, Nugent M, Pruhs K, Scquizzato M (2019) A $$o(n)$$- competitive deterministic algorithm for online matching on a line. Algorithmica 81:2917\u20132933","journal-title":"Algorithmica"},{"key":"1036_CR5","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/s00453-012-9676-9","volume":"68","author":"N Bansal","year":"2014","unstructured":"Bansal N, Buchbinder N, Gupta A, Naor JS (2014) A randomized $$O(\\log ^2k)$$-competitive algorithm for metric bipartite matching. Algorithmica 68:390\u2013403","journal-title":"Algorithmica"},{"key":"1036_CR6","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.orl.2021.12.005","volume":"50","author":"SVS Duppala","year":"2022","unstructured":"Duppala SVS, Sankararaman KA, Xu P (2022) Online minimum matching with uniform metric and random arrivals. Oper Res Lett 50:45\u201349","journal-title":"Oper Res Lett"},{"issue":"1","key":"1036_CR7","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.tcs.2004.10.028","volume":"332","author":"B Fuchs","year":"2005","unstructured":"Fuchs B, Hochstattler W, Kern W (2005) Online matching on a line. Theor Comput Sci 332(1):251\u2013264","journal-title":"Theor Comput Sci"},{"key":"1036_CR8","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.orl.2019.01.002","volume":"47","author":"M Gairing","year":"2019","unstructured":"Gairing M, Klimm M (2019) Greedy metric minimum online matchings with random arrivals. Oper Res Lett 47:88\u201391","journal-title":"Oper Res Lett"},{"key":"1036_CR9","doi-asserted-by":"crossref","unstructured":"Gupta A, Lewi K (2012) The online metric matching problem for doubling metrics. In: Proceedings of International Colloquium on Automata, Languages, and Programming (ICALP), pp 424\u2013435","DOI":"10.1007\/978-3-642-31594-7_36"},{"key":"1036_CR10","unstructured":"Idury R, Schaffer A (1992) A better lower bound for on-line bottleneck matching. Manuscript"},{"key":"1036_CR11","doi-asserted-by":"publisher","first-page":"2150156","DOI":"10.1142\/S1793830921501561","volume":"13","author":"T Itoh","year":"2021","unstructured":"Itoh T, Miyazaki S, Satake M (2021) Competitive analysis for two variants of online metric matching problem. Discrete Math Algorithms Appl 13:2150156","journal-title":"Discrete Math Algorithms Appl"},{"key":"1036_CR12","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram B, Pruhs K (1993) Online weighted matching. J Algorithms 14(3):478\u2013488. Preliminary version appeared in SODA, pp 231\u2013240, 1991","DOI":"10.1006\/jagm.1993.1026"},{"key":"1036_CR13","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/BFb0029573","volume":"1442","author":"B Kalyanasundaram","year":"1998","unstructured":"Kalyanasundaram B, Pruhs K (1998) Online network optimization problems. Lecture Notes in Computer Science 1442:268\u2013280","journal-title":"Lecture Notes in Computer Science"},{"issue":"1\u20132","key":"1036_CR14","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(99)00140-1","volume":"233","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram B, Pruhs K (2000a) An optimal deterministic algorithm for online b-matching. Theor Comput Sci 233(1\u20132):319\u2013325","journal-title":"Theor Comput Sci"},{"issue":"3","key":"1036_CR15","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1137\/S0895480198342310","volume":"13","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram B, Pruhs K (2000b) The online transportation problem. SIAM J Discrete Math 13(3):370\u2013383","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"1036_CR16","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S Khuller","year":"1994","unstructured":"Khuller S, Mitchell SG, Vazirani VV (1994) On-line algorithms for weighted bipartite matching and stable marriages. Theor Comput Sci 127(2):255\u2013267","journal-title":"Theor Comput Sci"},{"key":"1036_CR17","doi-asserted-by":"crossref","unstructured":"Meyerson A, Nanavati A, Poplawski L (2006) Randomized online algorithms for minimum metric bipartite matching. In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (SODA) pp 954\u2013959","DOI":"10.1145\/1109557.1109662"},{"key":"1036_CR18","doi-asserted-by":"crossref","unstructured":"Nayyar K, Raghvendra S (2017) An input sensitive online algorithm for the metric bipartite matching problem. In: Proceedings of IEEE 58th annual symposium on foundations of computer science, pp 505\u2013515","DOI":"10.1109\/FOCS.2017.53"},{"key":"1036_CR19","doi-asserted-by":"crossref","unstructured":"Peserico E, Scquizzato M (2021) Matching on the line admits no $$o(\\sqrt{\\log n})$$-competitive algorithm. In: Proceedings of the 48th international colloquium on automata, languages, and programming (ICALP), pp 103:1\u2013103:3","DOI":"10.1145\/3594873"},{"key":"1036_CR20","unstructured":"Raghvendra S (2016) A robust and optimal online algorithm for minimum metric bipartite matching. In: Proceedings of approximation, randomization, and combinatorial optimization. Algorithms and Techniques (APPROX\/RANDOM), pp 18:1\u201318:1"},{"key":"1036_CR21","unstructured":"Raghvendra S (2018) Optimal analysis of an online algorithm for the bipartite matching problem on a line. In: Proceedings of the 34th international symposium on computational geometry, pp 67:1\u201367:14"},{"key":"1036_CR22","doi-asserted-by":"publisher","first-page":"217","DOI":"10.3390\/computation10120217","volume":"10","author":"M Xiao","year":"2022","unstructured":"Xiao M, Yang Y, Li W (2022) Online bottleneck matching problem with two heterogeneous sensors in a metric space. Computation 10:217","journal-title":"Computation"},{"key":"1036_CR23","doi-asserted-by":"crossref","unstructured":"Xiao M, Li W (2022a) Online semi-matching problem with two heterogeneous sensors in a metric space. In: Proceedings of the 28th international computing and combinatorics conference, pp 444\u2013451","DOI":"10.1007\/978-3-031-22105-7_39"},{"key":"1036_CR24","doi-asserted-by":"crossref","unstructured":"Xiao M, Zhao S, Li W, Yang J (2021) Online bottleneck semi-matching. In: Proceedings of the 15th international conference on combinatorial optimization and applications, pp 445\u2013455","DOI":"10.1007\/978-3-030-92681-6_35"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01036-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-023-01036-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01036-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T07:57:38Z","timestamp":1702367858000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-023-01036-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1036"],"URL":"https:\/\/doi.org\/10.1007\/s10878-023-01036-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5]]},"assertion":[{"value":"20 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors haven\u2019t disclosed any conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"108"}}