DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.52

A Tight Competitive Ratio for Online Submodular Welfare Maximization

Authors: Amit Ganz, Pranav Nuti, and Roy Schwartz

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

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.

Cite as

Amit Ganz, Pranav Nuti, and Roy Schwartz. A Tight Competitive Ratio for Online Submodular Welfare Maximization. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ESA.2023.52},
  URN =		{urn:nbn:de:0030-drops-187052},
  doi =		{10.4230/LIPIcs.ESA.2023.52},
  annote =	{Keywords: Online Algorithms, Submodular Maximization, Welfare Maximization, Approximation Algorithms}
}

Search Results

Documents authored by Ganz, Amit

A Tight Competitive Ratio for Online Submodular Welfare Maximization

Abstract

Cite as

Thanks for your feedback!

Could not send message