2026-08-10T18:26:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10143 2024-03-06T10:45:29Z ddc:004 open_access

Semi-Online Bipartite Matching Kumar, Ravi Purohit, Manish Schild, Aaron Svitkina, Zoya Vee, Erik Semi-Online Algorithms Bipartite Matching In this paper we introduce the semi-online model that generalizes the classical online computational model. The semi-online model postulates that the unknown future has a predictable part and an adversarial part; these parts can be arbitrarily interleaved. An algorithm in this model operates as in the standard online model, i.e., makes an irrevocable decision at each step. We consider bipartite matching in the semi-online model. Our main contributions are competitive algorithms for this problem and a near-matching hardness bound. The competitive ratio of the algorithms nicely interpolates between the truly offline setting (i.e., no adversarial part) and the truly online setting (i.e., no predictable part). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ravi Kumar and Manish Purohit and Aaron Schild and Zoya Svitkina and Erik Vee 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.50 urn:nbn:de:0030-drops-101436 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.50 eng https://creativecommons.org/licenses/by/3.0/legalcode