Content deleted Content added
→Submodular set function maximization: we do not need a page number within a journal article whose entire topic is this claim, and whose abstract states this claim, and our citation templates do not provide a mechanism for augmenting journal articles with page numbers that are not the whole range of page numbers for the whole article |
m Open access bot: url-access updated in citation with #oabot. |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 25:
=== Non-monotone ===
A submodular function that is not monotone is called ''non-monotone''. In particular, a function is called non-monotone if it has the property that adding more elements to a set can decrease the value of the function. More formally, the function <math> f </math> is non-monotone if there are sets <math>S,T</math> in its ___domain s.t. <math> S \subset T </math> and <math>f(S)> f(T)</math>.
==== Symmetric ====
A non-monotone submodular function <math>f</math> is called ''symmetric'' if for every <math>S\subseteq \Omega</math> we have that <math>f(S)=f(\Omega-S)</math>.
Line 52 ⟶ 51:
=== Multilinear extension ===
Consider any vector <math>\mathbf{x}=\{x_1,x_2,\ldots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the multilinear extension is defined as <ref>{{Cite book |last=Vondrak |first=Jan |title=Proceedings of the fortieth annual ACM symposium on Theory of computing |chapter=Optimal approximation for the submodular welfare problem in the value oracle model |date=2008-05-17 |chapter-url=https://doi.org/10.1145/1374376.1374389 |series=STOC '08 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=67–74 |doi=10.1145/1374376.1374389 |isbn=978-1-60558-047-0|s2cid=170510 }}</ref><ref>{{Cite journal |last1=Calinescu |first1=Gruia |last2=Chekuri |first2=Chandra |last3=Pál |first3=Martin |last4=Vondrák |first4=Jan |date=January 2011 |title=Maximizing a Monotone Submodular Function Subject to a Matroid Constraint |url=http://epubs.siam.org/doi/10.1137/080733991 |journal=SIAM Journal on Computing |language=en |volume=40 |issue=6 |pages=1740–1766 |doi=10.1137/080733991 |issn=0097-5397|url-access=subscription }}</ref><math>F(\mathbf{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)</math>.
Intuitively, ''x<sub>i</sub>'' represents the probability that item ''i'' is chosen for the set. For every set ''S'', the two inner products represent the probability that the chosen set is exactly ''S''. Therefore, the sum represents the expected value of ''f'' for the set formed by choosing each item ''i'' at random with probability xi, independently of the other items.
Line 113 ⟶ 112:
<ref name="IFF">{{cite journal |first1=S. |last1=Iwata |first2=L. |last2=Fleischer |first3=S. |last3=Fujishige |title=A combinatorial strongly polynomial algorithm for minimizing submodular functions |journal=J. ACM |volume=48 |year=2001 |issue=4 |pages=761–777 |doi=10.1145/502090.502096 |s2cid=888513 }}</ref>
<ref name="Schrijver">{{cite journal |author-link=Alexander Schrijver |first=A. |last=Schrijver |title=A combinatorial algorithm minimizing submodular functions in strongly polynomial time |journal=J. Combin. Theory Ser. B |volume=80 |year=2000 |issue=2 |pages=346–355 |doi=10.1006/jctb.2000.1989 |url=https://ir.cwi.nl/pub/2108 |doi-access=free }}</ref>
<ref name="IJB">R. Iyer, [[Stefanie Jegelka|S. Jegelka]] and J. Bilmes, Fast Semidifferential based submodular function optimization, Proc. ICML (2013).</ref>
<ref name="IB">R. Iyer and J. Bilmes, Submodular Optimization Subject to Submodular Cover and Submodular Knapsack Constraints, In Advances of NIPS (2013).</ref>
<ref name="IBUAI">R. Iyer and J. Bilmes, Algorithms for Approximate Minimization of the Difference between Submodular Functions, In Proc. UAI (2012).</ref>
Line 131 ⟶ 130:
<ref name="FNS">M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).</ref>
<ref name="L">{{cite book |author-link1=László Lovász |last1=Lovász |first1=L. |title=Mathematical Programming the State of the Art |chapter=Submodular functions and convexity |date=1983 |chapter-url= |pages=235–257 |doi=10.1007/978-3-642-68874-4_10 |isbn=978-3-642-68876-8 |s2cid=117358746 }}</ref>
<ref name="BF">{{cite encyclopedia |last1=Buchbinder |first1=Niv |last2=Feldman |first2=Moran |title=Submodular Functions Maximization Problems |encyclopedia= Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications |year=2018 |editor1-last=Gonzalez |editor1-first=Teofilo F. |publisher=Chapman and Hall/CRC |doi=10.1201/9781351236423 |isbn=9781351236423 |url=https://www.taylorfrancis.com/chapters/edit/10.1201/9781351236423-42/submodular-functions-maximization-problems-niv-buchbinder-moran-feldman|url-access=subscription }}</ref>
<ref name="JV2">{{Cite web|last=Vondrák|first=Jan|title=Polyhedral techniques in combinatorial optimization: Lecture 17|url=https://theory.stanford.edu/~jvondrak/CS369P/lec17.pdf}}</ref>
| |||