{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:12:03Z","timestamp":1759335123862,"version":"build-2065373602"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T00:00:00Z","timestamp":1751932800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T00:00:00Z","timestamp":1751932800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/100016848","name":"National Chengchi University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100016848","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s00224-025-10230-1","type":"journal-article","created":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T05:44:39Z","timestamp":1751953479000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line"],"prefix":"10.1007","volume":"69","author":[{"given":"Tung-Wei","family":"Kuo","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,8]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Emek, Y., Kutten, S., Wattenhofer, R.: Online matching: haste makes waste! In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pp. 333\u2013344 (2016). https:\/\/doi.org\/10.1145\/2897518.2897557","key":"10230_CR1","DOI":"10.1145\/2897518.2897557"},{"doi-asserted-by":"publisher","unstructured":"Azar, Y., Chiplunkar, A., Kaplan, H.: Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 1051\u20131061 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.67","key":"10230_CR2","DOI":"10.1137\/1.9781611974782.67"},{"doi-asserted-by":"publisher","unstructured":"Ashlagi, I., Azar, Y., Charikar, M., Chiplunkar, A., Geri, O., Kaplan, H., Makhijani, R., Wang, Y., Wattenhofer, R.: Min-cost bipartite perfect matching with delays. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM) (2017). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.1","key":"10230_CR3","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2017.1"},{"doi-asserted-by":"publisher","unstructured":"Antoniadis, A., Barcelo, N., Nugent, M., Pruhs, K., Scquizzato, M.: A [CDATA[o(n)]]$$o(n)$$-competitive deterministic algorithm for online matching on a line. In: International Workshop on Approximation and Online Algorithms, Springer, pp. 11\u201322 (2014). https:\/\/doi.org\/10.1007\/s00453-019-00565-w","key":"10230_CR4","DOI":"10.1007\/s00453-019-00565-w"},{"doi-asserted-by":"publisher","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004). https:\/\/doi.org\/10.1016\/j.jcss.2004.04.011. Special Issue on STOC 2003","key":"10230_CR5","DOI":"10.1016\/j.jcss.2004.04.011"},{"doi-asserted-by":"publisher","unstructured":"Bienkowski, M., Kraska, A., Schmidt, P.: A match in time saves nine: Deterministic online matching with delays. In: International Workshop on Approximation and Online Algorithms, Springer, pp. 132\u2013146 (2017). https:\/\/doi.org\/10.1007\/978-3-319-89441-6_11","key":"10230_CR6","DOI":"10.1007\/978-3-319-89441-6_11"},{"doi-asserted-by":"publisher","unstructured":"Bienkowski, M., Kraska, A., Liu, H.-H., Schmidt, P.: A primal-dual online deterministic algorithm for matching with delays. In: International Workshop on Approximation and Online Algorithms, Springer, pp. 51\u201368 (2018). https:\/\/doi.org\/10.1007\/978-3-030-04693-4_4","key":"10230_CR7","DOI":"10.1007\/978-3-030-04693-4_4"},{"issue":"4","key":"10230_CR8","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/s00224-019-09963-7","volume":"64","author":"Y Azar","year":"2020","unstructured":"Azar, Y., Jacob-Fanani, A.: Deterministic min-cost matching with delays. Theory Comput. Syst. 64(4), 572\u2013592 (2020). https:\/\/doi.org\/10.1007\/s00224-019-09963-7","journal-title":"Theory Comput. Syst."},{"key":"10230_CR9","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.tcs.2018.07.004","volume":"754","author":"Y Emek","year":"2019","unstructured":"Emek, Y., Shapiro, Y., Wang, Y.: Minimum cost perfect matching with delays for two sources. Theoretical Comput. Sci. 754, 122\u2013129 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2018.07.004","journal-title":"Theoretical Comput. Sci."},{"doi-asserted-by":"publisher","unstructured":"Raghvendra, S.: A robust and optimal online algorithm for minimum metric bipartite matching. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2016) (2016). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.18. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","key":"10230_CR10","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.18"},{"doi-asserted-by":"publisher","unstructured":"Nayyar, K., Raghvendra, S.: An input sensitive online algorithm for the metric bipartite matching problem. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 505\u2013515 (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.53","key":"10230_CR11","DOI":"10.1109\/FOCS.2017.53"},{"doi-asserted-by":"publisher","unstructured":"Raghvendra, S.: Optimal analysis of an online algorithm for the bipartite matching problem on a line. In: 34th International Symposium on Computational Geometry (SoCG 2018) (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.67. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","key":"10230_CR12","DOI":"10.4230\/LIPIcs.SoCG.2018.67"},{"issue":"6","key":"10230_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3556971","volume":"69","author":"M Fahrbach","year":"2022","unstructured":"Fahrbach, M., Huang, Z., Tao, R., Zadimoghaddam, M.: Edge-weighted online bipartite matching. J. ACM 69(6), 1\u201335 (2022). https:\/\/doi.org\/10.1145\/3556971","journal-title":"J. ACM"},{"doi-asserted-by":"publisher","unstructured":"Kaplan, H., Naori, D., Raz, D.: Online weighted matching with a sample. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 1247\u20131272 (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.52","key":"10230_CR14","DOI":"10.1137\/1.9781611977073.52"},{"doi-asserted-by":"publisher","unstructured":"Huang, Z., Shu, X., Yan, S.: The power of multiple choices in online stochastic matching. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 91\u2013103 (2022). https:\/\/doi.org\/10.1145\/3519935.3520046","key":"10230_CR15","DOI":"10.1145\/3519935.3520046"},{"doi-asserted-by":"publisher","unstructured":"Buchbinder, N., Naor, J., Wajc, D.: Lossless online rounding for online bipartite matching (despite its impossibility). In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 2030\u20132068 (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch78","key":"10230_CR16","DOI":"10.1137\/1.9781611977554.ch78"},{"doi-asserted-by":"publisher","unstructured":"Yan, S.: Edge-weighted online stochastic matching: Beating $$1-\\frac{1}{e}$$[CDATA[1-\\frac{1}{e}]]. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4631\u20134640 (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.165","key":"10230_CR17","DOI":"10.1137\/1.9781611977912.165"},{"doi-asserted-by":"publisher","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends\u00ae Theoretical Comput. Sci. 8(4), 265\u2013368 (2013). https:\/\/doi.org\/10.1561\/0400000057","key":"10230_CR18","DOI":"10.1561\/0400000057"},{"doi-asserted-by":"publisher","unstructured":"Matuschke, J., Schmidt-Kraepelin, U., Verschae, J.: Maintaining Perfect Matchings at Low Cost. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 82\u201318214. Schloss Dagstuhl\u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.82","key":"10230_CR19","DOI":"10.4230\/LIPIcs.ICALP.2019.82"},{"doi-asserted-by":"publisher","unstructured":"Gupta, V., Krishnaswamy, R., Sandeep, S.: Permutation strikes back: The power of recourse in online metric matching. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2020) (2020). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.40. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik","key":"10230_CR20","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.40"},{"doi-asserted-by":"publisher","unstructured":"Megow, N., N\u00f6lke, L.: Online minimum cost matching with recourse on the line. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2020) (2020). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.37. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik","key":"10230_CR21","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.37"},{"issue":"4","key":"10230_CR22","doi-asserted-by":"publisher","first-page":"974","DOI":"10.1007\/s10878-020-00641-w","volume":"40","author":"S Angelopoulos","year":"2020","unstructured":"Angelopoulos, S., D\u00fcrr, C., Jin, S.: Online maximum matching with recourse. J. Combinatorial Optim. 40(4), 974\u20131007 (2020). https:\/\/doi.org\/10.1007\/s10878-020-00641-w","journal-title":"J. Combinatorial Optim."},{"doi-asserted-by":"publisher","unstructured":"Bhore, S., Filtser, A., Toth, C.D.: Online duet between metric embeddings and minimum-weight perfect matchings. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4564\u20134579 (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.162","key":"10230_CR23","DOI":"10.1137\/1.9781611977912.162"},{"doi-asserted-by":"publisher","unstructured":"Mari, M., Paw\u0142owski, M., Ren, R., Sankowski, P.: Online matching with delays and stochastic arrival times. Theory Comput. Syst. 69(12) (2025). https:\/\/doi.org\/10.1007\/s00224-024-10207-6","key":"10230_CR24","DOI":"10.1007\/s00224-024-10207-6"},{"issue":"4","key":"10230_CR25","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0210050","volume":"10","author":"EM Reingold","year":"1981","unstructured":"Reingold, E.M., Tarjan, R.E.: On a greedy heuristic for complete matching. SIAM J. Comput. 10(4), 676\u2013681 (1981). https:\/\/doi.org\/10.1137\/0210050","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"publisher","unstructured":"Liu, X., Pan, Z., Wang, Y., Wattenhofer, R.: Impatient online matching. In: 29th International Symposium on Algorithms and Computation (ISAAC 2018), vol. 123, pp. 62\u20131 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.62. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik","key":"10230_CR26","DOI":"10.4230\/LIPIcs.ISAAC.2018.62"},{"doi-asserted-by":"publisher","unstructured":"Azar, Y., Ren, R., Vainstein, D.: The min-cost matching with concave delays problem. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 301\u2013320 (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.20. SIAM","key":"10230_CR27","DOI":"10.1137\/1.9781611976465.20"},{"doi-asserted-by":"publisher","unstructured":"Deryckere, L., Umboh, S.W.: Online matching with set and concave delays. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2023) (2023). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2023.17. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik","key":"10230_CR28","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2023.17"},{"issue":"4","key":"10230_CR29","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM (JACM) 39(4), 745\u2013763 (1992). https:\/\/doi.org\/10.1145\/146585.146588","journal-title":"J. ACM (JACM)"},{"unstructured":"Melnyk, D., Wang, Y., Wattenhofer, R.: Online k-Way Matching with Delays and the H-Metric (2021). arXiv:2109.06640","key":"10230_CR30"},{"key":"10230_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114988","volume":"1026","author":"N Kakimura","year":"2025","unstructured":"Kakimura, N., Nakayoshi, T.: Deterministic primal-dual algorithms for online k-way matching with delays. Theoretical Comput. Sci. 1026, 114988 (2025). https:\/\/doi.org\/10.1016\/j.tcs.2024.114988","journal-title":"Theoretical Comput. Sci."},{"unstructured":"Ashlagi, I., Burq, M., Dutta, C., Jaillet, P., Saberi, A., Sholley, C.: Maximum Weight Online Matching with Deadlines (2018). arXiv:1808.03526","key":"10230_CR32"},{"doi-asserted-by":"publisher","unstructured":"Azar, Y., Touitou, N.: General framework for metric optimization problems with delay or with deadlines. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 60\u201371 (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00013","key":"10230_CR33","DOI":"10.1109\/FOCS.2019.00013"},{"doi-asserted-by":"publisher","unstructured":"Azar, Y., Touitou, N.: Beyond tree embeddings\u2013a deterministic framework for network design with deadlines or delay. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 1368\u20131379 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00129","key":"10230_CR34","DOI":"10.1109\/FOCS46700.2020.00129"},{"doi-asserted-by":"publisher","unstructured":"Azar, Y., Ganesh, A., Ge, R., Panigrahi, D.: Online service with delay. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 551\u2013563 (2017). https:\/\/doi.org\/10.1145\/3055399.3055475","key":"10230_CR35","DOI":"10.1145\/3055399.3055475"},{"doi-asserted-by":"publisher","unstructured":"Touitou, N.: Improved and deterministic online service with deadlines or delay. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 761\u2013774 (2023). https:\/\/doi.org\/10.1145\/3564246.3585107","key":"10230_CR36","DOI":"10.1145\/3564246.3585107"},{"doi-asserted-by":"publisher","unstructured":"Azar, Y., Lewkowicz, S., Vainstein, D.: List Update with Delays or Time Windows. In: Bringmann, K., Grohe, M., Puppis, G., Svensson, O. (eds.) 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 297, pp. 15\u201311520. Schloss Dagstuhl\u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2024.15","key":"10230_CR37","DOI":"10.4230\/LIPIcs.ICALP.2024.15"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10230-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10230-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10230-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T05:21:09Z","timestamp":1759296069000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10230-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,8]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10230"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10230-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,7,8]]},"assertion":[{"value":"30 June 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2025","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 declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"28"}}