Submodular set function: Difference between revisions

Revision as of 21:09, 15 June 2019

Revision as of 09:31, 16 June 2019

Line 80:

{{reflist|30em|

refs=

<ref name="GLS">{{cite journal |authorlink=Martin Grötschel |first=M. |last=Gr&ouml;tschelGrötschel |authorlink2=László Lovász |first2=L. |last2=Lovasz |authorlink3=Alexander Schrijver |first3=A. |last3=Schrijver |title=The ellipsoid method and its consequences in combinatorial optimization |journal=Combinatorica |volume=1 |issue=2 |year=1981 |pages=169–197 |doi=10.1007/BF02579273 }}</ref>

<ref name="Cunningham">{{cite journal |first=W. H. |last=Cunningham |title=On submodular function minimization |journal=Combinatorica |volume=5 |issue=3 |year=1985 |pages=185–192 |doi=10.1007/BF02579361 }}</ref>

<ref name="IFF">{{cite journal |first=S. |last=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 }}</ref>

Line 88:

<ref name="IBUAI">R. Iyer and J. Bilmes, Algorithms for Approximate Minimization of the Difference between Submodular Functions, In Proc. UAI (2012).</ref>

<ref name="NB">M. Narasimhan and J. Bilmes, A submodular-supermodular procedure with applications to discriminative structure learning, In Proc. UAI (2005).</ref>

<ref name="FMV">[[Uriel Feige|U. Feige]], V. Mirrokni and J. Vondr&aacute;kVondrák, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.</ref>

<ref name="NVF">[[George Nemhauser|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>

<ref name="CCPV">G. Calinescu, C. Chekuri, M. P&aacute;lPál and J. Vondr&aacute;kVondrák, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.</ref>

<ref name="BFNS">N. Buchbinder, M. Feldman, J. Naor and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, Proc. of 53rd FOCS (2012), pp. 649-658.</ref>

<ref name="FW">Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.</ref>

<ref name="SF">Z. Svitkina and L. Fleischer, Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on Computing (2011).</ref>

<ref name="JV">J. Vondr&aacute;kVondrák, Optimal approximation for the submodular welfare problem in the value oracle model, Proc. of STOC (2008), pp. 461–471.</ref>

<ref name="ST">http://submodularity.org/.</ref>

<ref name="KG">A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008</ref>