Maximizing non-monotone submodular set functions subject to different constraints: Combined algorithms

Salman Fadaei, MohammadAmin Fazli, MohammadAli Safari

Type: Article

Publication Date: 2011-10-15

Citations: 15

DOI: https://doi.org/10.1016/j.orl.2011.10.002

View Publication

Download PDF

Locations

Operations Research Letters - View
arXiv (Cornell University) - View - PDF
CiteSeer X (The Pennsylvania State University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Maximizing Non-monotone Submodular Set Functions Subject to Different Constraints: Combined Algorithms	2011	Salman Fadaei MohammadAmin Fazli MohammadAli Safari
+	Maximizing Non-monotone Submodular Set Functions Subject to Different Constraints: Combined Algorithms	2011	Salman Fadaei MohammadAmin Fazli MohammadAli Safari
+ PDF Chat	Improved Deterministic Algorithms for Non-monotone Submodular Maximization	2022	Xiaoming Sun Jialin Zhang Shuo Zhang Zhijie Zhang
+ PDF Chat	Improved deterministic algorithms for non-monotone submodular maximization	2023	Xiaoming Sun Jialin Zhang Shuo Zhang Zhijie Zhang
+	Algorithms for maximizing monotone submodular function minus modular function under noise	2023	Shufang Gong Bin Liu Mengxue Geng Qizhi Fang
+ PDF Chat	Robust Monotone Submodular Function Maximization	2016	James B. Orlin Andreas S. Schulz Rajan Udwani
+ PDF Chat	Robust monotone submodular function maximization	2018	James B. Orlin Andreas S. Schulz Rajan Udwani
+	Maximization of Nonsubmodular Functions under Multiple Constraints with Applications	2023	Lintao Ye Zhi‐Wei Liu 明政池 Vijay Gupta
+ PDF Chat	New performance guarantees for the greedy maximization of submodular set functions	2016	Jussi Laitila Atte Moilanen
+ PDF Chat	Maximization of nonsubmodular functions under multiple constraints with applications	2023	Lintao Ye Zhi‐Wei Liu 明政池 Vijay Gupta
+ PDF Chat	Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms	2010	Anupam Gupta Aaron Roth Grant Schoenebeck Kunal Talwar
+ PDF Chat	Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems	2024	Xiankun Yan Aneta Neumann Frank Neumann
+	The maximization of submodular functions	1999	Boris Goldengorin Gerardus Sierksma Michael Tso
+ PDF Chat	Partial-monotone adaptive submodular maximization	2022	Shaojie Tang Jing Yuan
+	Minimizing a sum of submodular functions	2012	Vladimir Kolmogorov
+	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
+ PDF Chat	Maximizing a Submodular Function with Viability Constraints	2015	Wolfgang Dvořák Monika Henzinger David P. Williamson
+ PDF Chat	Maximizing a Submodular Function with Viability Constraints	2013	Wolfgang Dvořák Monika Henzinger David P. Williamson
+ PDF Chat	Maximizing monotone submodular functions over the integer lattice	2018	Tasuku Soma Yuichi Yoshida

Works That Cite This (5)

Action	Title	Year	Authors
+ PDF Chat	Improved deterministic algorithms for non-monotone submodular maximization	2023	Xiaoming Sun Jialin Zhang Shuo Zhang Zhijie Zhang
+ PDF Chat	Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint	2022	Georgios Amanatidis Federico Fusco Philip Lazos Stefano Leonardi Rebecca Reiffenhäuser
+	Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings	2019	Vanja Doskoč Tobias Friedrich Andreas Göbel Frank Neumann Aneta Neumann Francesco Quinzan
+	Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint	2020	Georgios Amanatidis Federico Fusco Philip Lazos Stefano Leonardi Rebecca Reiffenhäuser
+	Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint	2020	Georgios Amanatidis Federico Fusco Philip Lazos Stefano Leonardi Rebecca Reiffenhäuser

Works Cited by This (11)

Action	Title	Year	Authors
+	Randomized Pipage Rounding for Matroid Polytopes and Applications	2009	Chandra Chekuri Jan Vondrák
+	A note on concentration of submodular functions	2010	J. Vondrák
+	Submodular Functions: Extensions, Distributions, and Algorithms. A Survey	2009	Shaddin Dughmi
+ PDF Chat	Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms	2010	Anupam Gupta Aaron Roth Grant Schoenebeck Kunal Talwar
+	Dependent Randomized Rounding for Matroid Polytopes and Applications	2009	Chandra Chekuri J. Vondrák Rico Zenklusen
+	Submodular function maximization via the multilinear relaxation and contention resolution schemes	2011	Chandra Chekuri Jan Vondrák Rico Zenklusen
+ PDF Chat	Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming	1995	Michel X. Goemans David P. Williamson
+ PDF Chat	Non-monotone submodular maximization under matroid and knapsack constraints	2009	Jon Lee Vahab Mirrokni Viswanath Nagarajan Maxim Sviridenko
+ PDF Chat	Symmetry and Approximability of Submodular Maximization Problems	2009	J. Vondrák
+ PDF Chat	Submodular Maximization by Simulated Annealing	2011	Shayan Oveis Gharan Jan Vondrák