{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T22:57:57Z","timestamp":1774393077080,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":24,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819778003","type":"print"},{"value":"9789819778010","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-97-7801-0_11","type":"book-chapter","created":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T18:05:37Z","timestamp":1726769137000},"page":"123-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Bottleneck Matching on\u00a0a\u00a0Star"],"prefix":"10.1007","author":[{"given":"Man","family":"Xiao","sequence":"first","affiliation":[]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"11_CR1","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.: Greedy metric minimum online matchings with random arrivals. Oper. Res. Lett. 47, 88\u201391 (2019)","journal-title":"Oper. Res. Lett."},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.orl.2021.12.005","volume":"50","author":"S Duppala","year":"2022","unstructured":"Duppala, S., Sankararaman, K., Xu, P.: Online minimum matching with uniform metric and random arrivals. Oper. Res. Lett. 50, 45\u201349 (2022)","journal-title":"Oper. Res. Lett."},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends\u00ae Theor. Comput. Sci. 8(4), 265\u2013368 (2013)","DOI":"10.1561\/0400000057"},{"key":"11_CR4","unstructured":"Idury, R., Schaffer, A.: A better lower bound for on-line bottleneck matching. Manuscript (1992)"},{"issue":"3","key":"11_CR5","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/s10878-012-9581-9","volume":"27","author":"B Anthony","year":"2014","unstructured":"Anthony, B., Chung, C.: Online bottleneck matching. J. Comb. Optim. 27(1), 100\u2013114 (2014)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"11_CR7","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1007\/s10878-015-9948-9","volume":"32","author":"B Anthony","year":"2016","unstructured":"Anthony, B., Chung, C.: Serve or skip: the power of rejection in online bottleneck matching. J. Comb. Optim. 32(4), 1232\u20131253 (2016)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"11_CR8","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, S., Vazirani, V.: On-line algorithms for weighted bipartite matching and stable marriages. Theoret. Comput. Sci. 127(2), 255\u2013267 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR9","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.: Online bottleneck matching problem with two heterogeneous sensors in a metric space. Computation 10, 217 (2022)","journal-title":"Computation"},{"key":"11_CR10","unstructured":"Raghvendra, S.: 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 (2016)"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Nanavati, A., Poplawski, L.: Randomized online algorithms for minimum metric bipartite matching. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 954\u2013959 (2006)","DOI":"10.1145\/1109557.1109662"},{"key":"11_CR12","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, J.: A randomized $$O(\\log ^2k)$$-competitive algorithm for metric bipartite matching. Algorithmica 68, 390\u2013403 (2014)","journal-title":"Algorithmica"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/BFb0029573","volume-title":"Online Algorithms","author":"B Kalyanasundaram","year":"1998","unstructured":"Kalyanasundaram, B., Pruhs, K.: On-line network optimization problems. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. LNCS, vol. 1442, pp. 268\u2013280. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0029573"},{"issue":"1","key":"11_CR14","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.: Online matching on a line. Theoret. Comput. Sci. 332(1), 251\u2013264 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/978-3-642-31594-7_36","volume-title":"Automata, Languages, and Programming","author":"A Gupta","year":"2012","unstructured":"Gupta, A., Lewi, K.: The online metric matching problem for doubling metrics. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 424\u2013435. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_36"},{"key":"11_CR16","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.: A $$o(n)$$-competitive deterministic algorithm for online matching on a line. Algorithmica 81, 2917\u20132933 (2019)","journal-title":"Algorithmica"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Nayyar, K., Raghvendra, S.: An input sensitive online algorithm for the metric bipartite matching problem. In: Proceedings of IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 505\u2013515 (2017)","DOI":"10.1109\/FOCS.2017.53"},{"key":"11_CR18","unstructured":"Raghvendra, S.: Optimal analysis of an online algorithm for the bipartite matching problem on a line. In: Proceedings of the 34th International Symposium on Computational Geometry (SoCG), pp. 67:1\u201367:14 (2018)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Peserico, E., Scquizzato, M.: 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 (2021)","DOI":"10.1145\/3594873"},{"key":"11_CR20","doi-asserted-by":"publisher","unstructured":"Xiao, M., Li, W.: Online semi-matching problem with two heterogeneous sensors in a metric space. In: Zhang, Y., Miao, D., M\u00f6hring, R. (eds.) COCOON 2022. LNCS, vol. 13595, pp. 444\u2013451. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-22105-7_39","DOI":"10.1007\/978-3-031-22105-7_39"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-030-92681-6_35","volume-title":"Combinatorial Optimization and Applications","author":"M Xiao","year":"2021","unstructured":"Xiao, M., Zhao, S., Li, W., Yang, J.: Online bottleneck semi-matching. In: Du, D.-Z., Du, D., Wu, C., Xu, D. (eds.) COCOA 2021. LNCS, vol. 13135, pp. 445\u2013455. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-92681-6_35"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/s10878-023-01036-3","volume":"45","author":"M Xiao","year":"2023","unstructured":"Xiao, M., Zhao, S., Li, W., Yang, J.: Online bottleneck matching on a line. J. Comb. Optim. 45, 108 (2023)","journal-title":"J. Comb. Optim."},{"key":"11_CR23","doi-asserted-by":"publisher","unstructured":"Harada, T., Itoh, T.: Competitive analysis of online facility assignment for general layout of servers on a line (2023). https:\/\/doi.org\/10.48550\/arXiv.2308.05933","DOI":"10.48550\/arXiv.2308.05933"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2022.06.007","volume":"928","author":"X Guo","year":"2022","unstructured":"Guo, X., Luo, K., Tang, Z., Zhang, Y.: The online food delivery problem on stars. Theoret. Comput. Sci. 928, 13\u201326 (2022)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-7801-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T18:08:29Z","timestamp":1726769309000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-7801-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819778003","9789819778010"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-7801-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Aspects in Information and Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dallas, TX","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/AAIM2024\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}