Online submodular maximization: beating 1/2 made simple
From MaRDI portal
Publication:5918911
DOI10.1007/s10107-019-01459-zzbMath1453.68215arXiv1807.05529OpenAlexW2951195910WikidataQ126460829 ScholiaQ126460829MaRDI QIDQ5918911
Yuval Filmus, Niv Buchbinder, Mohit Garg, Moran Feldman
Publication date: 28 August 2020
Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.05529
Nonlinear programming (90C30) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26) Online algorithms; streaming algorithms (68W27)
Related Items (7)
The Power of Subsampling in Submodular Maximization ⋮ Analyzing Residual Random Greedy for monotone submodular maximization ⋮ Two-stage submodular maximization under knapsack and matroid constraints ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Unnamed Item ⋮ Online submodular maximization: beating 1/2 made simple ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An optimal deterministic algorithm for online \(b\)-matching
- Online matroid intersection: beating half for random arrival
- Bayesian Mechanism Design
- Online Stochastic Matching: Online Actions Based on Offline Statistics
- Maximizing Non-monotone Submodular Functions
- Online Stochastic Weighted Matching: Improved Approximation Algorithms
- Maximum Matching in Semi-streaming with Few Passes
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
- AdWords and generalized online matching
- Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
- Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems
- Online Stochastic Matching: Beating 1-1/e
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization
- Fast algorithms for maximizing submodular functions
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Online submodular welfare maximization: Greedy is optimal
- Online submodular maximization: beating 1/2 made simple
This page was built for publication: Online submodular maximization: beating 1/2 made simple
