Online submodular welfare maximization: Greedy is optimal

DOI10.1137/1.9781611973105.88zbMath1425.91198arXiv1204.1025OpenAlexW2949270856MaRDI QIDQ5741797

Michael Kapralov, Jan Vondrák, Ian Post

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.1025

Mathematics Subject Classification ID

Combinatorial optimization (90C27) 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 (19)

Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice ⋮ Streaming algorithms for maximizing DR-submodular functions with \(d\)-knapsack constraints ⋮ Competitive online algorithms for resource allocation over the positive semidefinite cone ⋮ Unnamed Item ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice ⋮ A mobile multi-agent sensing problem with submodular functions under a partition matroid ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Streaming submodular maximization under \(d\)-knapsack constraints ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ Unnamed Item ⋮ Maximizing monotone submodular functions over the integer lattice ⋮ Unnamed Item ⋮ Online submodular maximization: beating 1/2 made simple ⋮ Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

This page was built for publication: Online submodular welfare maximization: Greedy is optimal