Submodular set function: Difference between revisions

Revision as of 07:29, 29 October 2012

Revision as of 17:10, 16 November 2012

Line 63:

{{reflist|

refs=

<ref name="GLS">M. GrotschelGr&ouml;tschel, [[László Lovász|L. Lovasz]], and [[Alexander Schrijver|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">[[Alexander 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">[[Uriel Feige|U. Feige]], V. Mirrokni and J. Vondr´ak.&aacute;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;l and J. Vondra&aacute;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>

}}