DocumentCode
2226547
Title
Maximizing Non-Monotone Submodular Functions
Author
Feige, Uriel ; Mirrokni, Vahab S. ; Vondrák, Jan
Author_Institution
Wetzmann Inst., Rehovot
fYear
2007
fDate
21-23 Oct. 2007
Firstpage
461
Lastpage
471
Abstract
Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard.
Keywords
computational complexity; directed graphs; function approximation; optimisation; search problems; NP-hard problem; computational complexity; constraint satisfaction problem; maximum facility location problem; nonmonotone submodular function; submodular maximization; undirected graph; Algorithm design and analysis; Approximation algorithms; Computer science; Greedy algorithms; Mathematics; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on
Conference_Location
Providence, RI
ISSN
0272-5428
Print_ISBN
978-0-7695-3010-9
Type
conf
DOI
10.1109/FOCS.2007.29
Filename
4389516
Link To Document