arXiv preprint ·
Online Submodular Welfare Maximization: Computation is not the Bottleneck
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching, display ads and AdWords. A natural greedy OSW algorithm achieves a competitive ratio of $1/2$ [LLN06], and $1-1/e$ under i.i.d. arrivals [KPV13]. Both bounds are tight for polynomial-time algorithms unless NP=RP [KPV13]. The information-theoretic limits for OSW, in contrast, remained open. This prompted researchers to ask for tighter upper bounds [Mehta13] or conjecture the existence of better-competitive (slow) algorithms [Huang23, LTX+23, CHS24, Huang2024, HTW24}. We resolve Mehta's question and refute the subsequent conjectures, proving that the greedy algorithm is in fact tight for both adversarial and i.i.d. arrivals, regardless of computation time. Seemingly contradicting recent $(1-1/e)$-competitive fractional algorithms for OSW [HJP+24,Patton26], we show that this impossibility even holds for fractional algorithms, provided their outputs correspond to marginals that are roundable in hindsight. Conceptually, our proofs can be seen as identifying that a bottleneck for OSW, even under (deterministic) adversarial arrivals, is the inherently random notion of correlation gap [ADSY12].
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Mean Field Model of Consumption Inertia and Keeping Up with the Joneses
Convex-Analytic View of Query Selection for Safety Verification of Markov Decision Processes
Risk-Averse Inference-Time Diffusion Model Alignment with Finite-Sample Guarantees
Exploration strategies for Gaussian process bandit optimization with inference regret guarantees
On integrability of local utility maximizing strategies
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.