Online submodular welfare maximization: greedy is optimal

DOI10.1137/1.9781611973105.88zbMATH Open1425.91198arXiv1204.1025OpenAlexW2949270856MaRDI QIDQ5741797FDOQ5741797

Authors: Michael Kapralov, Ian Post, Jan Vondrák 

Publication date: 15 May 2019

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

Abstract: We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless $NP=RP$. Since the Greedy algorithm is known to be 1/2-competitive for monotone submodular valuations, of which coverage is a special case, this proves that Greedy provides the optimal competitive ratio. On the other hand, we prove that Greedy in a stochastic setting with i.i.d.items and valuations satisfying diminishing returns is $(1-1/e)$-competitive, which is optimal even for coverage valuations, unless $NP=RP$. For online budget-additive allocation, we prove that no algorithm can be 0.612-competitive with respect to a natural LP which has been used previously for this problem.

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

Recommendations

• Online submodular welfare maximization: greedy beats 1/2 in random order
• Online submodular maximization: beating 1/2 made simple
• Online submodular maximization: beating 1/2 made simple
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Optimal approximation for the submodular welfare problem in the value oracle model

Mathematics Subject Classification ID

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

Cited In (25)

• Title not available (Why is that?)
• Adwords in a panorama
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• Online Submodular Maximization with Free Disposal
• A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions
• Online submodular maximization: beating 1/2 made simple
• Optimal approximation for the submodular welfare problem in the value oracle model
• Two-sided capacitated submodular maximization in gig platforms
• Competitive online algorithms for resource allocation over the positive semidefinite cone
• Streaming algorithms for maximizing DR-submodular functions with \(d\)-knapsack constraints
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Title not available (Why is that?)
• Title not available (Why is that?)
• A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
• A mobile multi-agent sensing problem with submodular functions under a partition matroid
• Maximizing monotone submodular functions over the integer lattice
• Submodular optimization problems and greedy strategies: a survey
• Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
• A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
• Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
• Edge-weighted online bipartite matching
• Streaming submodular maximization under \(d\)-knapsack constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741797)