2026-07-19T13:04:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18705 2024-03-06T11:02:31Z ddc:004 open_access

A Tight Competitive Ratio for Online Submodular Welfare Maximization Ganz, Amit Nuti, Pranav Schwartz, Roy Online Algorithms Submodular Maximization Welfare Maximization Approximation Algorithms In this paper we consider the online Submodular Welfare (SW) problem. In this problem we are given n bidders each equipped with a general non-negative (not necessarily monotone) submodular utility and m items that arrive online. The goal is to assign each item, once it arrives, to a bidder or discard it, while maximizing the sum of utilities. When an adversary determines the items' arrival order we present a simple randomized algorithm that achieves a tight competitive ratio of 1/4. The algorithm is a specialization of an algorithm due to [Harshaw-Kazemi-Feldman-Karbasi MOR`22], who presented the previously best known competitive ratio of 3-2√2≈ 0.171573 to the problem. When the items' arrival order is uniformly random, we present a competitive ratio of ≈ 0.27493, improving the previously known 1/4 guarantee. Our approach for the latter result is based on a better analysis of the (offline) Residual Random Greedy (RRG) algorithm of [Buchbinder-Feldman-Naor-Schwartz SODA`14], which we believe might be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amit Ganz and Pranav Nuti and Roy Schwartz 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.52 urn:nbn:de:0030-drops-187052 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.52 eng https://creativecommons.org/licenses/by/4.0/legalcode