Online Submodular Welfare Maximization

DOI10.1145/2746539.2746626zbMath1322.91031OpenAlexW2162765276MaRDI QIDQ2941586

Nitish Korula, Morteza Zadimoghaddam, Vahab S. Mirrokni

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2746539.2746626

zbMATH Keywords

online algorithmssubmodular optimizationrandom-orderonline SWMsecond-order submodular functionssubmodular welfare maximization

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Auctions, bargaining, bidding and selling, and other market models (91B26) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Online algorithms; streaming algorithms (68W27) Welfare economics (91B15)

Related Items (7)

The Limitations of Optimization from Samples ⋮ Approximation algorithms for the partial assignment problem ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ Unnamed Item ⋮ Performance bounds with curvature for batched greedy optimization

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Online Submodular Welfare Maximization