Online Submodular Maximization: Beating 1/2 Made Simple

Niv Buchbinder, Moran Feldman, Yuval Filmus, Mohit Garg

Type: Book-Chapter

Publication Date: 2019-01-01

Citations: 7

DOI: https://doi.org/10.1007/978-3-030-17953-3_8

View Publication

Download PDF

Locations

Lecture notes in computer science - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Online submodular maximization: beating 1/2 made simple	2020	Niv Buchbinder Moran Feldman Yuval Filmus Mohit Garg
+	Robust Submodular Maximization: Offline and Online Algorithms.	2017	Nima Anari Nika Haghtalab Joseph Naor Sebastian Pokutta Mohit Singh Alfredo Torrico
+	Online dynamic submodular optimization	2024	Antoine Lesage‐Landry Julien Pallage
+ PDF Chat	Very Fast Streaming Submodular Function Maximization	2021	Sebastian Buschjäger Philipp-Jan Honysz Lukas Pfahler Katharina Morik
+ PDF Chat	Streaming Algorithms for Submodular Function Maximization	2015	Chandra Chekuri Shalmoli Gupta Kent Quanrud
+ PDF Chat	Submodular Maximization Meets Streaming: Matchings, Matroids, and More	2014	Amit Chakrabarti Sagar Kale
+ PDF Chat	Submodular maximization meets streaming: matchings, matroids, and more	2015	Amit Chakrabarti Sagar Kale
+ PDF Chat	Practical Budgeted Submodular Maximization	2022	Moran Feldman Zeev Nutov Elad Shoham
+ PDF Chat	Beyond pointwise submodularity: Non-monotone adaptive submodular maximization in linear time	2020	Shaojie Tang
+ PDF Chat	Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline	2015	Lisa Hellerstein Devorah Kletenik Patrick Lin
+ PDF Chat	Scale-Free Algorithms for Online Linear Optimization	2015	Francesco Orabona Dávid Pál
+ PDF Chat	Guess Free Maximization of Submodular and Linear Sums	2020	Moran Feldman
+ PDF Chat	Guess Free Maximization of Submodular and Linear Sums	2019	Moran Feldman
+ PDF Chat	Partial-Adaptive Submodular Maximization	2023	Shaojie Tang Jing Yuan
+	Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity	2021	Georgios Amanatidis Federico Fusco Philip Lazos Stefano Leonardi Alberto Marchetti-Spaccamela Rebecca Reiffenhäuser
+	Online partial least square optimization: dropping convexity for better efficiency and scalability	2017	Zhehui Chen Lin F. Yang Chris Junchi Li Tuo Zhao
+ PDF Chat	Derandomization for k-Submodular Maximization	2018	Hiroki Oshima
+	Submodular optimization problems and greedy strategies: A survey	2020	Yajing Liu Edwin K. P. Chong Ali Pezeshki Zhenliang Zhang
+	An Optimal Algorithm for Online Unconstrained Submodular Maximization.	2018	Tim Roughgarden Joshua R. Wang
+ PDF Chat	Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms	2010	Anupam Gupta Aaron Roth Grant Schoenebeck Kunal Talwar

Works That Cite This (3)

Action	Title	Year	Authors
+ PDF Chat	Online submodular maximization: beating 1/2 made simple	2020	Niv Buchbinder Moran Feldman Yuval Filmus Mohit Garg
+ PDF Chat	Online Submodular Maximization: Beating 1/2 Made Simple	2019	Niv Buchbinder Moran Feldman Yuval Filmus Mohit Garg
+	The Power of Subsampling in Submodular Maximization	2021	Christopher Harshaw Ehsan Kazemi Moran Feldman Amin Karbasi

Works Cited by This (13)

Action	Title	Year	Authors
+	Online vertex-weighted bipartite matching and single-bid budgeted allocations	2011	Gagan Aggarwal Gagan Goel Chinmay Karande Aranyak Mehta
+ PDF Chat	Maximum Matching in Semi-streaming with Few Passes	2012	Christian Konrad Frédéric Magniez Claire Mathieu
+ PDF Chat	Near optimal online algorithms and fast approximation algorithms for resource allocation problems	2011	Nikhil R. Devanur Kamal Jain Balasubramanian Sivan Christopher A. Wilkens
+ PDF Chat	Online Stochastic Matching: Beating 1-1/e	2009	Jon Feldman Aranyak Mehta Vahab Mirrokni S. Muthukrishnan
+ PDF Chat	Comparing Apples and Oranges: Query Trade-off in Submodular Maximization	2016	Niv Buchbinder Moran Feldman Roy Schwartz
+ PDF Chat	Online Stochastic Matching: Online Actions Based on Offline Statistics	2012	Vahideh Manshadi Shayan Oveis Gharan Amin Saberi
+	Beyond $1/2$-Approximation for Submodular Maximization on Massive Data Streams	2018	Ashkan Norouzi-Fard Jakub Tarnawski Slobodan Mitrović Amir Zandieh Aida Mousavifar Ola Svensson
+ PDF Chat	Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order	2018	Nitish Korula Vahab Mirrokni Morteza Zadimoghaddam
+ PDF Chat	Online Submodular Maximization: Beating 1/2 Made Simple	2019	Niv Buchbinder Moran Feldman Yuval Filmus Mohit Garg
+ PDF Chat	Online submodular welfare maximization: Greedy is optimal	2013	Michael Kapralov Ian Post Jan Vondrák