Symmetry and approximability of submodular maximization problems

Jan Vondrák

Type: Preprint

Publication Date: 2011-10-21

Citations: 1

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Symmetry and approximability of submodular maximization problems	2011	Jan Vondrák
+ PDF Chat	Symmetry and Approximability of Submodular Maximization Problems	2013	J. Vondrák
+ PDF Chat	Symmetry and Approximability of Submodular Maximization Problems	2009	J. Vondrák
+ PDF Chat	Subquadratic Submodular Maximization with a General Matroid Constraint	2024	Yusuke Kobayashi Tatsuya Terao
+	Constrained Submodular Maximization via a Non-symmetric Technique	2016	Niv Buchbinder Moran Feldman
+	Constrained Submodular Maximization via a Non-symmetric Technique	2016	Niv Buchbinder Moran Feldman
+ PDF Chat	Constrained Submodular Maximization via a Nonsymmetric Technique	2019	Niv Buchbinder Moran Feldman
+ PDF Chat	Sparsification of Decomposable Submodular Functions	2022	Akbar Rafiey Yuichi Yoshida
+	Sparsification of Decomposable Submodular Functions	2022	Akbar Rafiey Yuichi Yoshida
+ PDF Chat	Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization	2024	Niv Buchbinder Moran Feldman
+	Instance Specific Approximations for Submodular Maximization	2021	Eric Balkanski Sharon Qian Yaron Singer
+	Multivariate Submodular Optimization	2016	Richard Santiago F. Bruce Shepherd
+ PDF Chat	Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint	2024	Niv Buchbinder Moran Feldman
+	Submodular Functions: Extensions, Distributions, and Algorithms. A Survey	2009	Shaddin Dughmi
+ PDF Chat	The Submodular Secretary Problem Goes Linear	2018	Moran Feldman Rico Zenklusen
+	Greed is Not Always Good: On Submodular Maximization over Independence Systems	2019	Alan Kuhnle
+	Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time	2020	Kai Han Zongmai Cao Shuang Cui Benwei Wu
+ PDF Chat	Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes	2014	Chandra Chekuri J. Vondrák Rico Zenklusen
+	A Note on Submodular Maximization over Independence Systems	2019	Alan Kuhnle
+	On the Approximation of Submodular Functions	2013	Nikhil R. Devanur Shaddin Dughmi Roy Schwartz Ankit Sharma Mohit Singh

Works That Cite This (1)

Action	Title	Year	Authors
+	TOPICS IN DISCRETE OPTIMIZATION: MODELS, COMPLEXITY AND ALGORITHMS	2013	Qie He

Works Cited by This (4)

Action	Title	Year	Authors
+	Submodular functions and convexity	1983	László Lovász
+	Matroids and the greedy algorithm	1971	Jack Edmonds
+ PDF Chat	The computational complexity of truthfulness in combinatorial auctions	2012	Shahar Dobzinski Jan Vondrák
+	Limitations of randomized mechanisms for combinatorial auctions	2011	Shaddin Dughmi Jan Vondrák