Content deleted Content added
m v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation - Heading start with three "=" and later with level two) |
m Open access bot: url-access updated in citation with #oabot. |
||
| (One intermediate revision by one other user not shown) | |||
Line 39:
=== Definition ===
Let <math>S</math> be a finite set. A set function <math>f: 2^S \to \mathbb{R}</math> is '''supermodular''' if it satifies the following (equivalent) conditions:<ref>{{Citation |last=McCormick |first=S. Thomas |title=Discrete Optimization |chapter=Submodular Function Minimization |date=2005 |series=Handbooks in Operations Research and Management Science |volume=12 |pages=321–391 |chapter-url=https://linkinghub.elsevier.com/retrieve/pii/S0927050705120076 |access-date=2024-12-12 |publisher=Elsevier |language=en |doi=10.1016/s0927-0507(05)12007-6 |isbn=978-0-444-51507-0}}</ref>
# <math> f(A)+f(B) \leq f(A \cap B) + f(A \cup B) </math> for all <math> A, B \subseteq S </math>.
Line 52:
== Optimization Techniques ==
There are specialized techniques for optimizing submodular functions. Theory and enumeration algorithms for finding local and global maxima (minima) of submodular (supermodular) functions can be found in "Maximization of submodular functions: Theory and enumeration algorithms", B. Goldengorin.<ref>{{Cite journal |last=Goldengorin |first=Boris |date=2009-10-01 |title=Maximization of submodular functions: Theory and enumeration algorithms |url=https://www.sciencedirect.com/science/article/pii/S0377221708007418 |journal=European Journal of Operational Research |language=en |volume=198 |issue=1 |pages=102–112 |doi=10.1016/j.ejor.2008.08.022 |issn=0377-2217|url-access=subscription }}</ref>
==See also==
| |||