{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T09:11:41Z","timestamp":1783761101785,"version":"3.55.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T00:00:00Z","timestamp":1783728000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T00:00:00Z","timestamp":1783728000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RTG 2236\/2"],"award-info":[{"award-number":["RTG 2236\/2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2026,9]]},"abstract":"Abstract<\/jats:title>\n \n In medical appointment assignment, unit jobs representing patients arrive online and are assigned to a time slot within their given feasible time interval. We model this setting as interval-constrained online bipartite matching problem. We consider a variant of this problem where reassignments are allowed and extend it by a notion of time that is decoupled from the job arrival events. As jobs arrive, the current point in time gradually advances, and once the time of a slot is passed, the job assigned to it is fixed and cannot be reassigned anymore. We analyze two algorithms for this problem with respect to the resulting matching size and the number of occurring reassignments. We show that FirstFit with reassignments according to the shortest augmenting path rule is exactly\n \n \n $$\\frac{2}{3}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -competitive with respect to the matching cardinality. The competitive ratio remains\n \n \n $$\\frac{2}{3}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n if we restrict FirstFit to consider only augmenting paths causing at most a constant number of reassignments, which implies a linear number of reassignments in total. This fills the gap between the known optimal algorithm with no reassignments at all, which is\n \n \n $$\\frac{1}{2}$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -competitive, on the one hand, and an earliest-deadline-first strategy (EDF), which we prove to be 1-competitive in our over-time framework, but which suffers\n \n \n $$\\Omega (n^2)$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n reassignments in the worst case, on the other. We further extend the problem setting to the sets of feasible slots per job that are not intervals. In this setting, FirstFit remains\n \n \n $$\\frac{2}{3}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -competitive, which is optimal with respect to the matching cardinality, while EDF loses its optimality.\n <\/jats:p>","DOI":"10.1007\/s00236-026-00543-0","type":"journal-article","created":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T08:12:55Z","timestamp":1783757575000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Interval-constrained bipartite matching over time"],"prefix":"10.1007","volume":"63","author":[{"given":"Andreas","family":"Abels","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mariia","family":"Anapolska","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christina","family":"B\u00fcsing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,11]]},"reference":[{"key":"543_CR1","doi-asserted-by":"publisher","unstructured":"Abels, A., Anapolska, M., B\u00fcsing, C.: Interval-constrained bipartite matching over time. In: Approximation and Online Algorithms, WAOA 2025. Lecture Notes in Computer Science, vol. 16077, pp. 1\u201317. Springer (2025). https:\/\/doi.org\/10.1007\/978-3-032-06706-7_1","DOI":"10.1007\/978-3-032-06706-7_1"},{"key":"543_CR2","doi-asserted-by":"publisher","unstructured":"Abels, A., Anapolska, M., B\u00fcsing, C.: Interval-constrained bipartite matching over time. In: Approximation and Online Algorithms, WAOA 2025. Lecture Notes in Computer Science, vol. 16077, pp. 1\u201317 (2025). https:\/\/doi.org\/10.1007\/978-3-032-06706-7_1","DOI":"10.1007\/978-3-032-06706-7_1"},{"key":"543_CR3","doi-asserted-by":"publisher","unstructured":"Baruah, S.K., Haritsa, J.R., Sharma, N.: On-line scheduling to maximize task completions. In: 15th Real-Time Systems Symposium, RTSS, pp. 228\u2013236. Springer (1994). https:\/\/doi.org\/10.1109\/REAL.1994.342713","DOI":"10.1109\/REAL.1994.342713"},{"key":"543_CR4","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Dudeja, A.: Online matching with recourse: Random edge arrivals. In: 40th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, pp. 11:1-11:16 (2020). https:\/\/doi.org\/10.4230\/LIPICS.FSTTCS.2020.11","DOI":"10.4230\/LIPICS.FSTTCS.2020.11"},{"key":"543_CR5","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Dudeja, A.: Online matching with recourse: Random edge arrivals. In: 40th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, pp. 11\u201311116. (2020). https:\/\/doi.org\/10.4230\/LIPICS.FSTTCS.2020.11","DOI":"10.4230\/LIPICS.FSTTCS.2020.11"},{"key":"543_CR6","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Kopelowitz, T., Pettie, S., Porat, E., Stein, C.: Simultaneously load balancing for every $$p$$-norm, with reassignments. 8th Innovations in Theoretical Computer Science Conference, ITCS 67, pp. 51:1-51:14 https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2017.51","DOI":"10.4230\/LIPICS.ITCS.2017.51"},{"key":"543_CR7","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Kopelowitz, T., Pettie, S., Porat, E., Stein, C.: Simultaneously load balancing for every $$p$$-norm, with reassignments. 8th Innovations in Theoretical Computer Science Conference, ITCS 67, 51\u201315114 (2017). https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2017.51","DOI":"10.4230\/LIPICS.ITCS.2017.51"},{"key":"543_CR8","doi-asserted-by":"publisher","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online bipartite matching in offline time. In: 55th Annual Symposium on Foundations of Computer Science, FOCS, pp. 384\u2013393. IEEE (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.48","DOI":"10.1109\/FOCS.2014.48"},{"key":"543_CR9","doi-asserted-by":"publisher","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online bipartite matching in offline time. In: 55th Annual Symposium on Foundations of Computer Science, FOCS, pp. 384\u2013393. (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.48","DOI":"10.1109\/FOCS.2014.48"},{"key":"543_CR10","doi-asserted-by":"publisher","unstructured":"Chaudhuri, K., Daskalakis, C., Kleinberg, R.D., Lin, H.: Online bipartite perfect matching with augmentations. In: 28th International Conference on Computer Communications, INFOCOM, pp. 1044\u20131052. IEEE (2009). https:\/\/doi.org\/10.1109\/infcom.2009.5062016","DOI":"10.1109\/infcom.2009.5062016"},{"key":"543_CR11","doi-asserted-by":"publisher","unstructured":"Chaudhuri, K., Daskalakis, C., Kleinberg, R.D., Lin, H.: Online bipartite perfect matching with augmentations. In: 28th International Conference on Computer Communications, INFOCOM, pp. 1044\u20131052. (2009). https:\/\/doi.org\/10.1109\/infcom.2009.5062016","DOI":"10.1109\/infcom.2009.5062016"},{"key":"543_CR12","doi-asserted-by":"publisher","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: 24th Annual Symposium on Discrete Algorithms, SODA, pp. 101\u2013107. SIAM (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.7","DOI":"10.1137\/1.9781611973105.7"},{"key":"543_CR13","doi-asserted-by":"publisher","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: 24th Annual Symposium on Discrete Algorithms, SODA, pp. 101\u2013107. (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.7","DOI":"10.1137\/1.9781611973105.7"},{"issue":"10","key":"543_CR14","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1503\/cmaj.050415","volume":"172","author":"L Eggertson","year":"2005","unstructured":"Eggertson, L.: Wait time alliance first to set benchmarks. CMAJ 172(10), 1277 (2005). https:\/\/doi.org\/10.1503\/cmaj.050415","journal-title":"CMAJ"},{"key":"543_CR15","doi-asserted-by":"publisher","unstructured":"Fiat, A., Woeginger, G.J.: Competitive analysis of algorithms, pp. 1\u201312. Springer (1998). https:\/\/doi.org\/10.1007\/BFb0029562","DOI":"10.1007\/BFb0029562"},{"key":"543_CR16","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: 19th Annual Symposium on Discrete Algorithms, SODA, pp. 982\u2013991. SIAM (2008). http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347189"},{"key":"543_CR17","doi-asserted-by":"publisher","unstructured":"Grove, E.F., Kao, M., Krishnan, P., Vitter, J.S.: Online perfect matching and mobile computing. 4th International Workshop on Algorithms and Data Structures, WADS 955, 194\u2013205. Springer (1995). https:\/\/doi.org\/10.1007\/3-540-60220-8_62","DOI":"10.1007\/3-540-60220-8_62"},{"key":"543_CR18","doi-asserted-by":"publisher","unstructured":"Gupta, A., Kumar, A., Stein, C.: Maintaining assignments online: Matching, scheduling, and flows. In: 25th Annual Symposium on Discrete Algorithms, SODA, pp. 468\u2013479. SIAM (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.35","DOI":"10.1137\/1.9781611973402.35"},{"key":"543_CR19","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, APPROX\/RANDOM, pp. 40:1-40:20 (2020). https:\/\/doi.org\/10.4230\/LIPICS.APPROX\/RANDOM.2020.40","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2020.40"},{"key":"543_CR20","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, APPROX\/RANDOM, pp. 40\u201314020. (2020). https:\/\/doi.org\/10.4230\/LIPICS.APPROX\/RANDOM.2020.40","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2020.40"},{"key":"543_CR21","doi-asserted-by":"publisher","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: 22nd Annual Symposium on Theory of Computing, STOC, pp. 352\u2013358. ACM (1990). https:\/\/doi.org\/10.1145\/100216.100262","DOI":"10.1145\/100216.100262"},{"key":"543_CR22","doi-asserted-by":"publisher","unstructured":"Korte, B.H., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, Springer (2018). https:\/\/doi.org\/10.1007\/978-3-662-56039-6","DOI":"10.1007\/978-3-662-56039-6"},{"key":"543_CR23","doi-asserted-by":"publisher","unstructured":"Liu, A.H., Toole-Charignon, J.: The power of amortized recourse for online graph problems. In: 20th International Workshop on Approximation and Online Algorithms, WAOA. Lecture Notes in Computer Science, pp. 134\u2013153. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-18367-6_7","DOI":"10.1007\/978-3-031-18367-6_7"},{"key":"543_CR24","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, APPROX\/RANDOM, pp. 37:1-37:16 (2020). https:\/\/doi.org\/10.4230\/LIPICS.APPROX\/RANDOM.2020.37","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2020.37"},{"key":"543_CR25","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, APPROX\/RANDOM, pp. 37\u201313716. (2020). https:\/\/doi.org\/10.4230\/LIPICS.APPROX\/RANDOM.2020.37","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2020.37"},{"key":"543_CR26","doi-asserted-by":"publisher","unstructured":"Shin, Y., Kim, K., Lee, S., An, H.: Online graph matching problems with a worst-case reassignment budget. CoRR arXiv:abs\/2003.05175 (2020) https:\/\/doi.org\/10.48550\/arXiv.2003.05175","DOI":"10.48550\/arXiv.2003.05175"},{"key":"543_CR27","doi-asserted-by":"publisher","unstructured":"Steiner, G., Yeomans, S.: A note on \u201cscheduling unit-time tasks with integer release times and deadlines.\u201d Inf. Process. Lett. 47, 165\u2013166 (1993). https:\/\/doi.org\/10.1016\/0020-0190(93)90241-Z","DOI":"10.1016\/0020-0190(93)90241-Z"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00543-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-026-00543-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00543-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T08:12:57Z","timestamp":1783757577000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-026-00543-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,11]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["543"],"URL":"https:\/\/doi.org\/10.1007\/s00236-026-00543-0","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,11]]},"assertion":[{"value":"12 December 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2026","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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"27"}}