Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

Alina Ene, Huy L. Nguyễn

Type: Preprint

Publication Date: 2018-01-01

Citations: 1

DOI: https://doi.org/10.48550/arxiv.1804.05379

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time	2019	Alina Ene Huy L. Nguyễn
+ PDF Chat	Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time	2019	Alina Ene Huy L. Nguyễn
+	Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity	2018	Matthew Fahrbach Vahab Mirrokni Morteza Zadimoghaddam
+ PDF Chat	Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity	2019	Matthew Fahrbach Vahab Mirrokni Morteza Zadimoghaddam
+	Non-monotone Submodular Maximization with Nearly Optimal Adaptivity Complexity.	2018	Matthew Fahrbach Vahab Mirrokni Morteza Zadimoghaddam
+	Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity	2018	Matthew Fahrbach Vahab Mirrokni Morteza Zadimoghaddam
+	Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity	2018	Matthew Fahrbach Vahab Mirrokni Morteza Zadimoghaddam
+ PDF Chat	An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation	2019	Eric Balkanski Aviad Rubinstein Yaron Singer
+	An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation	2018	Eric Balkanski Aviad Rubinstein Yaron Singer
+	Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization	2020	Alan Kuhnle
+	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
+ PDF Chat	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
+	A polynomial lower bound on adaptive complexity of submodular maximization	2020	Wenzheng Li Paul Liu J. Vondrák
+ PDF Chat	Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint	2024	Y.-M. Chen Alan Kuhnle
+	Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint	2020	Yixin Chen Alan Kuhnle
+	The FAST Algorithm for Submodular Maximization	2019	Adam Breuer Eric Balkanski Yaron Singer
+	An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model	2018	Eric Balkanski Aviad Rubinstein Yaron Singer
+	Linear-Time Algorithms for Adaptive Submodular Maximization	2020	Shaojie Tang
+	Optimal Algorithm and Lower Bound for Submodular Maximization	2020	Wenxin Li
+ PDF Chat	Unconstrained submodular maximization with constant adaptive complexity	2019	Lin Chen Moran Feldman Amin Karbasi

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	The Limitations of Optimization from Samples	2022	Eric Balkanski Aviad Rubinstein Yaron Singer

Works Cited by This (0)

Action	Title	Year	Authors