{"id":"arxiv/2610.16060","url":"https://arxiv.org/abs/2610.16060","tags":["cs.DS","math.OC"],"score":0,"title":"Online Submodular Welfare Maximization: Computation is not the Bottleneck","domain":"cs.DS","source":"arxiv","authors":["Rajan Udwani","David Wajc"],"reviews":0,"subject":"cs.DS","summary":"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)…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}