Improved Deterministic Algorithms for Non-monotone Submodular Maximization

Xiaoming Sun, Jialin Zhang, Shuo Zhang, Zhijie Zhang

Type: Preprint

Publication Date: 2022-01-01

Citations: 1

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

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions	2024	Zongqi Wan Jialin Zhang Xiaoming Sun Zhijie Zhang
+ PDF Chat	Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity	2024	Canh V. Pham
+	Improved Deterministic Streaming Algorithms for Non-monotone Submodular Maximization	2023	Xiaoming Sun Jialin Zhang Shuo Zhang
+ PDF Chat	A Tight Deterministic Algorithm for the Submodular Multiple Knapsack Problem	2020	Xiaoming Sun Jialin Zhang Zhijie Zhang
+	Nearly Linear Time Algorithms and Lower Bound for Submodular Maximization	2018	Wenxin Li Ness B. Shroff
+ PDF Chat	Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint	2021	Jing Tang Xueyan Tang Andrew Lim Kai Han Chongshou Li Junsong Yuan
+	Approximation Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with a Size Constraint.	2019	Shinsaku Sakaue
+	Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint	2019	Shinsaku Sakaue
+	Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint	2019	Shinsaku Sakaue
+ PDF Chat	Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint	2024	Niv Buchbinder Moran Feldman
+ 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
+ PDF Chat	Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint	2021	Jing Tang Xueyan Tang Andrew Lim Kai Han Chongshou Li Junsong Yuan
+	Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint	2021	Jing Tang Xueyan Tang Andrew Lim Kai Han Chongshou Li Junsong Yuan
+	Nearly Linear Time Deterministic Algorithms for Submodular Maximization Under Knapsack Constraint and Beyond	2018	Wenxin Li
+	Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time	2020	Kai Han Zongmai Cao Shuang Cui Benwei Wu
+	Nearly Linear-Time, Deterministic Algorithm for Maximizing (Non-Monotone) Submodular Functions Under Cardinality Constraint	2019	Alan Kuhnle
+	Nearly Linear-Time, Deterministic Algorithm for Maximizing (Non-Monotone) Submodular Functions Under Cardinality Constraint	2019	Alan Kuhnle
+	Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid	2018	Niv Buchbinder Moran Feldman Mohit Garg
+	Submodular Maximization with Matroid and Packing Constraints in Parallel	2018	Alina Ene Huy L. Nguyễn Adrian Vladu

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	Improved Deterministic Algorithms for Non-monotone Submodular Maximization	2022	Xiaoming Sun Jialin Zhang Shuo Zhang Zhijie Zhang

Works Cited by This (0)

Action	Title	Year	Authors