Content deleted Content added
Added types of submodular function and moved the examples to appropriate types. Also expanded the section on extensions. |
Improved the section on optimization, improved and added references, removed external links. |
||
Line 54:
Submodular functions have properties which are very similar to convex and concave functions. Hence a lot of optimization problems can be cast as maximizing or minimizing submodular functions subject to various constraints.
# Minimization of submodular functions.
#:Under the simplest case the problem is to find set <math>S\subseteq \Omega</math> which minimizes submodular function subject to no constraints. A series of results <ref name="GLS" /><ref name="Cunningham" /><ref name="IFF" /><ref name="Schrijver" /> have established the polynomial time solvability of this problem. Finding [[minimum cut]] in a graph is a special case of this problem.
# Maximization of submodular functions.
#:Unlike minimization, maximization of submodular functions is typically [[NP-hard]]. A host of problems such as [[max cut]], [[maximum coverage problem]] can be cast as special cases of this problem under suitable constraints. Typically the approximation algorithms for these problems are based on either greedy or local search type of algorithms.
## Maximizing a Symmetric Non-montone Submodular function subject to no constraint. This problem admits a 1/2 approximation algorithm<ref name="FMV" />. Finding [[max cut]] is a special case of this problem.
## Maximizing a Montone Submodular function subject to cardinality constraint. This problem admits a 1-1/e approximation algorithm<ref name="NVF" />. [[Maximum coverage problem]] is a special case of this problem.
==References==
{{reflist|
refs=
<ref name="SchrijverBook">Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency. Springer. ISBN-13: 978-3540443896 </ref>
<ref name="GLS">M. Grotschel, L. Lovasz, and A. Schrijver , The ellipsoid method and its consequences in combinatorial optimization,Combinatorica,1 (1981),pp. 169–197.</ref>
<ref name="Cunningham">W. H. Cunningham, On submodular function minimization, Combinatorica,5 (1985),pp. 185–192.</ref>
<ref name="IFF"> S. Iwata, L. Fleischer, and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions,J. ACM,48 (2001),pp. 761–777</ref>
<ref name="Schrijver">A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time,J. Combin. Theory Ser. B,80 (2000),pp. 346–355.</ref>
<ref name="FMV">U. Feige, V. Mirrokni and J. Vondr´ak. Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), 461–471.</ref>
<ref name="NVF"> G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I, Mathematical Programming 14 (1978), 265–294</ref>
}}
*{{Citation|last=Schrijver|first=Alexander|year=2003|title=Combinatorial Optimization|___location=|publisher=[[Springer]]|isbn=3540443894}}
*{{Citation|last=Lee|first=Jon|year= 2004 |title=A First Course in Combinatorial Optimization |___location=|publisher=[[Cambridge University Press]]|isbn= 0521010128}}
*{{Citation|last=Fujishige|first=Saruto|year=2005|title=Submodular Functions and Optimization|___location=|publisher=[[Elsevier]]|isbn=0444520864}}
*{{Citation|last=Narayanan|first=H.|year= 1997 |title=Submodular Functions and Electrical Networks|___location=|publisher=|isbn= 0444825231}}
== External links ==
<!--- Categories --->
| |||