Online Submodular Welfare Maximization: Computation is not the Bottleneck
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)…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.16060
curl -X POST /api/v1/records/arxiv/2610.16060/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16060/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'