TY - GEN
T1 - Nonmonotone submodular maximization via a structural continuous greedy algorithm
AU - Feldman, Moran
AU - Naor, Joseph
AU - Schwartz, Roy
PY - 2011
Y1 - 2011
N2 - Consider a suboptimal solution S for a maximization problem. Suppose S's value is small compared to an optimal solution OPT to the problem, yet S is structurally similar to OPT. A natural question in this setting is whether there is a way of improving S based solely on this information. In this paper we introduce the Structural Continuous Greedy Algorithm, answering this question affirmatively in the setting of the Nonmonotone Submodular Maximization Problem. We improve on the best approximation factor known for this problem. In the Nonmonotone Submodular Maximization Problem we are given a non-negative submodular function f, and the objective is to find a subset maximizing f. Our method yields an 0.42-approximation for this problem, improving on the current best approximation factor of 0.41 given by Gharan and Vondrák [5]. On the other hand, Feige et al. [4] showed a lower bound of 0.5 for this problem.
AB - Consider a suboptimal solution S for a maximization problem. Suppose S's value is small compared to an optimal solution OPT to the problem, yet S is structurally similar to OPT. A natural question in this setting is whether there is a way of improving S based solely on this information. In this paper we introduce the Structural Continuous Greedy Algorithm, answering this question affirmatively in the setting of the Nonmonotone Submodular Maximization Problem. We improve on the best approximation factor known for this problem. In the Nonmonotone Submodular Maximization Problem we are given a non-negative submodular function f, and the objective is to find a subset maximizing f. Our method yields an 0.42-approximation for this problem, improving on the current best approximation factor of 0.41 given by Gharan and Vondrák [5]. On the other hand, Feige et al. [4] showed a lower bound of 0.5 for this problem.
UR - https://www.scopus.com/pages/publications/79959946623
U2 - 10.1007/978-3-642-22006-7_29
DO - 10.1007/978-3-642-22006-7_29
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:79959946623
SN - 9783642220050
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 342
EP - 353
BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
PB - Springer Verlag
ER -