Submodular set function: Difference between revisions

Revision as of 00:55, 11 November 2023

Revision as of 18:25, 15 November 2023

Line 52:

=== 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 journalbook |last=Vondrak |first=Jan |datetitle=2008-05-17Proceedings of the fortieth annual ACM symposium on Theory of computing |titlechapter=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 |journal=Proceedings of the fortieth annual ACM symposium on Theory of computing |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 |lastlast1=Calinescu |firstfirst1=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}}</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_i'' 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 130:

<ref name="KG1">A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, UAI-2005.</ref>

<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 journalbook |author-link1=László Lovász |last1=Lovász |first1=L. |datetitle=1983Mathematical Programming the State of the Art |titlechapter=Submodular functions and convexity |urldate=1983 |journalchapter-url=Mathematical Programming the State of the Art |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}}</ref>

Line 141:

*{{Citation|last=Lee|first=Jon|author-link=Jon Lee (mathematician)|year= 2004 |title=A First Course in Combinatorial Optimization |publisher=[[Cambridge University Press]]|isbn= 0-521-01012-8}}

*{{Citation|last=Fujishige|first=Satoru|year=2005|title=Submodular Functions and Optimization|publisher=[[Elsevier]]|isbn=0-444-52086-4}}

*{{Citation|last=Narayanan|first=H.|year= 1997 |title=Submodular Functions and Electrical Networks|publisher=Elsevier |isbn= 0-444-82523-1}}

*{{citation | last=Oxley | first=James G. | title=Matroid theory | series=Oxford Science Publications | ___location=Oxford | publisher=[[Oxford University Press]] | year=1992 | isbn=0-19-853563-5 | zbl=0784.05002 }}