Online submodular welfare maximization: greedy is optimal

DOI10.1137/1.9781611973105.88MaRDI QIDQ5741797zbMATHOpenAlexFDO

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)

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

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)

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.

Recommendations

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

Cited in

(25)

• A mobile multi-agent sensing problem with submodular functions under a partition matroid
• Valuated matroid-based algorithm for submodular welfare problem
• A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
• Optimal approximation for the submodular welfare problem in the value oracle model
• A survey on double greedy algorithms for maximizing non-monotone submodular functions
• Two-sided capacitated submodular maximization in gig platforms
• Submodular optimization problems and greedy strategies: a survey
• Streaming submodular maximization under \(d\)-knapsack constraints
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• Edge-weighted online bipartite matching
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• Competitive online algorithms for resource allocation over the positive semidefinite cone
• scientific article; zbMATH DE number 7255156 (Why is no real title available?)
• Streaming algorithms for maximizing DR-submodular functions with \(d\)-knapsack constraints
• Submodular secretary problems: cardinality, matching, and linear constraints
• Profit sharing and efficiency in utility games
• Adwords in a panorama
• Online Submodular Maximization with Free Disposal
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
• Submodular secretary problem with shortlists
• 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
• Online submodular welfare maximization: greedy beats 1/2 in random order

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)