License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.52
URN: urn:nbn:de:0030-drops-187052
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18705/
Go to the corresponding LIPIcs Volume Portal

Ganz, Amit ; Nuti, Pranav ; Schwartz, Roy

A Tight Competitive Ratio for Online Submodular Welfare Maximization

pdf-format:
LIPIcs-ESA-2023-52.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ganz_et_al:LIPIcs.ESA.2023.52,
  author =	{Ganz, Amit and Nuti, Pranav and Schwartz, Roy},
  title =	{{A Tight Competitive Ratio for Online Submodular Welfare Maximization}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18705},
  URN =		{urn:nbn:de:0030-drops-187052},
  doi =		{10.4230/LIPIcs.ESA.2023.52},
  annote =	{Keywords: Online Algorithms, Submodular Maximization, Welfare Maximization, Approximation Algorithms}
}

Keywords: Online Algorithms, Submodular Maximization, Welfare Maximization, Approximation Algorithms
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI