5758:. Owing to the diminishing returns property, submodular functions naturally model costs of items, since there is often a larger discount, with an increase in the items one buys. Submodular functions model notions of complexity, similarity and cooperation when they appear in minimization problems. In maximization problems, on the other hand, they model notions of diversity, information and coverage.
4337:
4000:
5541:
3675:
4448:
775:
4167:
3830:
5725:
Minimization/maximization of a submodular function subject to a submodular level set constraint (also known as submodular optimization subject to submodular cover or submodular knapsack constraint) admits bounded approximation
3351:
5124:
1275:
1514:
4603:
389:
3510:
4123:
3786:
3219:
4705:
2680:
2250:
1619:
1411:
146:
5215:
2464:
2016:
1817:
510:
591:
3015:
5382:
4778:
4544:
1145:
2634:
sets. For example: we know that the value of receiving house A and house B is V, and we want to know the value of receiving 40% of house A and 60% of house B. To this end, we need a
291:
5729:
Partitioning data based on a submodular function to maximize the average welfare is known as the submodular welfare problem, which also admits bounded approximation guarantees (see
5377:
1187:
3554:
2833:
424:
233:
2336:
2781:
2494:
2280:
2046:
1888:
1649:
1540:
539:
4840:
4162:
3825:
3549:
3258:
1938:
5853:
3080:
6259:
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.
631:
2619:
2377:
2171:
3131:
1439:
1080:
5564:
which concerns optimizing a convex or concave function can also be described as the problem of maximizing or minimizing a submodular function subject to some constraints.
5144:
4933:
1036:
259:
2935:
2871:
2755:
2716:
1308:
173:
4350:
3373:
4996:
2561:
2113:
1334:
803:
197:
101:
2897:
2587:
2139:
913:
858:
5704:
5659:
5323:
5296:
5269:
5242:
4042:
2523:
2075:
1707:
1678:
5164:
5036:
5016:
4976:
4953:
4880:
4860:
4728:
4623:
4468:
3429:
3035:
2962:
1858:
1727:
1006:
973:
953:
933:
878:
823:
3409:
4332:{\displaystyle f^{+}(\mathbf {x} )=\max \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}
3995:{\displaystyle f^{-}(\mathbf {x} )=\min \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}
636:
6324:
G. Calinescu, C. Chekuri, M. Pál and J. Vondrák, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.
6342:
Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.
31:
that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit (
3265:
5608:
even in the unconstrained setting. Thus, most of the works in this field are concerned with polynomial-time approximation algorithms, including
6351:
M. Narasimhan and J. Bilmes, A submodular-supermodular procedure with applications to discriminative structure learning, In Proc. UAI (2005).
5718:
Apart from submodular minimization and maximization, there are several other natural optimization problems related to submodular functions.
6369:
R. Iyer and J. Bilmes, Submodular
Optimization Subject to Submodular Cover and Submodular Knapsack Constraints, In Advances of NIPS (2013).
5808:
S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning
Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.
5041:
6222:
Z. Svitkina and L. Fleischer, Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on
Computing (2011).
6152:
Iwata, S.; Fleischer, L.; Fujishige, S. (2001). "A combinatorial strongly polynomial algorithm for minimizing submodular functions".
1200:
6360:
R. Iyer and J. Bilmes, Algorithms for
Approximate Minimization of the Difference between Submodular Functions, In Proc. UAI (2012).
6333:
M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).
1444:
4549:
296:
3442:
5781:
4055:
3718:
3151:
5980:
5935:
4628:
2940:
2644:
2184:
1553:
1345:
110:
5169:
2398:
1950:
1751:
6539:
429:
544:
72:
6544:
6494:
6472:
6454:
6432:
6407:
5873:
5536:{\displaystyle \mathbb {E} \geq \sum _{R\subseteq }\Pi _{i\in R}p_{i}\Pi _{i\notin R}(1-p_{i})f(\cup _{i\in R}A_{i})}
3376:
2967:
6250:, V. Mirrokni and J. Vondrák, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.
5858:
Handbook of
Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications
2630:
Often, given a submodular set function that describes the values of various sets, we need to compute the values of
6272:; Wolsey, L. A.; Fisher, M. L. (1978). "An analysis of approximations for maximizing submodular set functions I".
1730:
5620:
The problem of maximizing a non-negative submodular function admits a 1/2 approximation algorithm. Computing the
4733:
1819:
be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.
4490:
1092:
3670:{\displaystyle F(\mathbf {x} )=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})}
3136:
Several kinds of continuous extensions of submodular functions are commonly used, which are described below.
264:
5328:
2019:
1545:
1150:
64:
2786:
397:
206:
5613:
2285:
5722:
Minimizing the difference between two submodular functions is not only NP hard, but also inapproximable.
2760:
2473:
2259:
2025:
1867:
1628:
1519:
518:
6424:
4786:
4128:
3791:
3515:
3224:
1893:
176:
5627:
The problem of maximizing a monotone submodular function subject to a cardinality constraint admits a
3040:
1542:
is called a coverage function. This can be generalized by adding non-negative weights to the elements.
5829:
A. Krause and C. Guestrin, Beyond
Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008
5817:
A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, UAI-2005.
1192:
596:
5572:
The hardness of minimizing a submodular set function depends on constraints imposed on the problem.
2592:
2341:
2144:
5889:
5662:
4443:{\displaystyle f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )}
3085:
1041:
782:
40:
5710:
Many of these algorithms can be unified within a semi-differential based framework of algorithms.
5129:
4885:
1015:
238:
6549:
6486:
6416:
2902:
2838:
2721:
2685:
1280:
151:
60:
56:
805:
is not assumed finite, then the above conditions are not equivalent. In particular a function
6238:
and J. Bilmes, Fast
Semidifferential based submodular function optimization, Proc. ICML (2013).
3358:
1419:
6308:
5767:
4981:
4480:
2528:
2080:
1313:
788:
182:
86:
6065:
5915:
3145:
2876:
2566:
2118:
883:
828:
5799:
H. Lin and J. Bilmes, A Class of
Submodular Functions for Document Summarization, ACL-2011.
5730:
5675:
5630:
5561:
5301:
5274:
5247:
5220:
51:. Recently, submodular functions have also found utility in several real world problems in
6504:
4008:
2499:
2051:
1683:
1654:
8:
6399:
6391:
6187:
6069:
6044:
5581:
36:
32:
6061:
6289:
6192:"A combinatorial algorithm minimizing submodular functions in strongly polynomial time"
6169:
6134:
6099:
5986:
5941:
5149:
5021:
5001:
4961:
4938:
4865:
4845:
4713:
4608:
4484:
4453:
3414:
3020:
2947:
2176:
1843:
1712:
991:
958:
938:
918:
863:
808:
770:{\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)}
48:
3382:
935:
is infinite satisfies the first condition above, but the second condition fails when
6517:
6490:
6468:
6450:
6428:
6403:
6293:
6025:
5976:
5945:
5931:
5869:
104:
68:
6138:
6103:
5967:. STOC '08. New York, NY, USA: Association for Computing Machinery. pp. 67–74.
5961:"Optimal approximation for the submodular welfare problem in the value oracle model"
6500:
6281:
6269:
6235:
6203:
6161:
6126:
6089:
6081:
6072:(1981). "The ellipsoid method and its consequences in combinatorial optimization".
6017:
5968:
5923:
5861:
5751:
5609:
5557:
5146:
is the empty set. More generally consider the following random process where a set
1622:
52:
6173:
5990:
5591:
The problem of minimizing a submodular function with a cardinality lower bound is
3695:, the two inner products represent the probability that the chosen set is exactly
6378:
J. Bilmes, Submodularity in
Machine Learning Applications, Tutorial at AAAI-2015.
5927:
5755:
5577:
5553:
2253:
1734:
2388:
A non-monotone submodular function which is not symmetric is called asymmetric.
5576:
The unconstrained problem of minimizing a submodular function is computable in
2621:. This can be generalized by adding non-negative weights to the directed edges.
2467:
6005:
6004:
Calinescu, Gruia; Chekuri, Chandra; Pál, Martin; Vondrák, Jan (January 2011).
6533:
6029:
5604:
Unlike the case of minimization, maximizing a generic submodular function is
3346:{\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}
5972:
5742:
Submodular functions naturally occur in several real world applications, in
6208:
6006:"Maximizing a Monotone Submodular Function Subject to a Matroid Constraint"
1743:
75:, sensor placement, image collection summarization and many other domains.
28:
6165:
5960:
5865:
6247:
5776:
5747:
5621:
5585:
44:
6094:
6285:
6130:
6085:
5965:
Proceedings of the fortieth annual ACM symposium on Theory of computing
1733:. Further inequalities for the entropy function are known to hold, see
6021:
5668:
The problem of maximizing a monotone submodular function subject to a
2173:. This can be generalized by adding non-negative weights to the edges.
5743:
2625:
39:
property which makes them suitable for many applications, including
6446:
1940:. Examples of symmetric non-monotone submodular functions include:
5595:, with polynomial factor lower bounds on the approximation factor.
6117:
Cunningham, W. H. (1985). "On submodular function minimization".
6045:"Polyhedral techniques in combinatorial optimization: Lecture 17"
5772:
5669:
5605:
5592:
5119:{\displaystyle \mathbb {E} \geq pf(\Omega )+(1-p)f(\varnothing )}
3707:
at random with probability xi, independently of the other items.
1740:
1414:
785:
function, but a subadditive function need not be submodular. If
5552:
Submodular functions have properties which are very similar to
1270:{\displaystyle f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}}
199:, which satisfies one of the following equivalent conditions.
6191:
978:
6523:
1509:{\displaystyle f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|}
6309:"Bridging Continuous and Discrete Optimization: Lecture 23"
4598:{\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}
3411:. The Lovász extension is a convex function if and only if
384:{\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}
6003:
5588:
in a graph is a special case of this minimization problem.
4342:
3505:{\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}
5672:
constraint (which subsumes the case above) also admits a
4347:
For the extensions discussed above, it can be shown that
4118:{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}
3781:{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}
3214:{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}
6060:
6151:
5599:
5567:
4935:
is submodular, for any non decreasing concave function
4700:{\displaystyle g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)}
4005:
The convex closure of any set function is convex over
3699:. Therefore, the sum represents the expected value of
577:
6268:
5678:
5633:
5385:
5331:
5304:
5277:
5250:
5223:
5172:
5152:
5132:
5044:
5024:
5004:
4984:
4964:
4941:
4888:
4868:
4848:
4789:
4736:
4716:
4631:
4611:
4552:
4493:
4456:
4353:
4170:
4131:
4058:
4011:
3833:
3794:
3721:
3557:
3518:
3445:
3417:
3385:
3361:
3268:
3227:
3154:
3088:
3043:
3023:
2970:
2950:
2905:
2879:
2841:
2789:
2763:
2724:
2688:
2675:{\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }
2647:
2595:
2569:
2531:
2502:
2476:
2401:
2344:
2288:
2262:
2245:{\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}
2187:
2147:
2121:
2083:
2054:
2028:
1953:
1896:
1870:
1846:
1828:
A submodular function that is not monotone is called
1754:
1715:
1686:
1657:
1631:
1614:{\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}
1556:
1522:
1447:
1422:
1406:{\displaystyle \Omega =\{E_{1},E_{2},\ldots ,E_{n}\}}
1348:
1316:
1283:
1203:
1153:
1095:
1082:. Examples of monotone submodular functions include:
1044:
1018:
994:
961:
941:
921:
886:
866:
831:
811:
791:
639:
599:
547:
521:
432:
400:
299:
267:
241:
209:
185:
154:
141:{\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }
113:
89:
5210:{\displaystyle 1\leq i\leq l,A_{i}\subseteq \Omega }
2459:{\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}
2011:{\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}
1812:{\displaystyle \Omega =\{e_{1},e_{2},\dots ,e_{n}\}}
505:{\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}
6518:http://www.cs.berkeley.edu/~stefje/references.html
5698:
5653:
5535:
5371:
5317:
5290:
5263:
5236:
5209:
5158:
5138:
5118:
5030:
5010:
4990:
4970:
4947:
4927:
4874:
4854:
4834:
4772:
4722:
4699:
4617:
4597:
4538:
4462:
4442:
4331:
4156:
4117:
4036:
3994:
3819:
3780:
3669:
3543:
3504:
3423:
3403:
3367:
3345:
3252:
3213:
3125:
3074:
3029:
3009:
2956:
2929:
2891:
2865:
2827:
2775:
2749:
2710:
2674:
2613:
2581:
2555:
2517:
2488:
2458:
2371:
2330:
2274:
2244:
2165:
2133:
2107:
2069:
2040:
2010:
1932:
1882:
1852:
1811:
1721:
1701:
1672:
1643:
1613:
1534:
1508:
1433:
1405:
1328:
1302:
1269:
1181:
1139:
1074:
1030:
1000:
967:
947:
927:
907:
872:
852:
817:
797:
769:
625:
586:{\displaystyle x_{1},x_{2}\in \Omega \backslash X}
585:
533:
504:
418:
383:
285:
253:
227:
191:
167:
140:
95:
5851:
2626:Continuous extensions of submodular set functions
6531:
5713:
4805:
4195:
3858:
1219:
3551:. Then the multilinear extension is defined as
5918:(1983). "Submodular functions and convexity".
3010:{\displaystyle F:^{n}\rightarrow \mathbb {R} }
1709:is the entropy of the set of random variables
5920:Mathematical Programming the State of the Art
5624:of a graph is a special case of this problem.
1147:is called a linear function. Additionally if
47:(as functions modeling user preferences) and
6465:Submodular Functions and Electrical Networks
6421:A First Course in Combinatorial Optimization
5854:"Submodular Functions Maximization Problems"
4112:
4067:
3775:
3730:
3499:
3454:
3334:
3307:
3208:
3163:
3144:This extension is named after mathematician
3063:
3050:
2816:
2803:
2738:
2725:
2453:
2408:
2239:
2194:
2005:
1960:
1806:
1761:
1608:
1563:
1400:
1355:
975:are infinite sets with finite intersection.
781:A nonnegative submodular function is also a
746:
720:
699:
686:
665:
652:
360:
354:
318:
312:
6116:
6110:
4773:{\displaystyle g(S)=f(\Omega \setminus S)}
3260:. Then the Lovász extension is defined as
979:Types and examples of submodular functions
107:, a submodular function is a set function
6462:
6440:
6390:
6207:
6186:
6180:
6093:
5839:
5387:
5046:
4862:is a real number, is submodular whenever
4539:{\displaystyle f_{1},f_{2},\ldots ,f_{k}}
4164:. Then the concave closure is defined as
3703:for the set formed by choosing each item
3294:
3003:
2668:
134:
6526:includes further material on the subject
5852:Buchbinder, Niv; Feldman, Moran (2018).
5547:
5379:. Then the following inequality is true
5038:. Then the following inequality is true
4882:is monotone submodular. More generally,
3827:. Then the convex closure is defined as
3434:
1140:{\displaystyle f(S)=\sum _{i\in S}w_{i}}
16:Set-to-real map with diminishing returns
6485:, Oxford Science Publications, Oxford:
5958:
5166:is constructed as follows. For each of
4343:Relations between continuous extensions
286:{\displaystyle x\in \Omega \setminus Y}
6532:
6306:
6230:
6228:
5914:
5782:Utility functions on indivisible goods
5372:{\displaystyle S=\cup _{i=1}^{l}S_{i}}
4958:Consider a random process where a set
6480:
6443:Submodular Functions and Optimization
6354:
5890:"Information Processing and Learning"
4479:The class of submodular functions is
3691:is chosen for the set. For every set
3687:represents the probability that item
1182:{\displaystyle \forall i,w_{i}\geq 0}
6318:
6253:
5825:
5823:
5600:Submodular set function maximization
5568:Submodular set function minimization
2828:{\displaystyle x^{S}\in \{0,1\}^{n}}
2718:can be represented as a function on
419:{\displaystyle S,T\subseteq \Omega }
228:{\displaystyle X,Y\subseteq \Omega }
6415:
6327:
6262:
6241:
6225:
6145:
6054:
6042:
6036:
5802:
4487:. Consider any submodular function
3139:
2331:{\displaystyle f(S)=I(S;\Omega -S)}
1840:A non-monotone submodular function
1413:be a collection of subsets of some
13:
6372:
6363:
6345:
6336:
6216:
5899:
5811:
5665:is a special case of this problem.
5461:
5435:
5204:
5080:
4985:
4758:
4047:
3586:
2776:{\displaystyle S\subseteq \Omega }
2770:
2694:
2659:
2602:
2489:{\displaystyle S\subseteq \Omega }
2483:
2402:
2357:
2316:
2275:{\displaystyle S\subseteq \Omega }
2269:
2188:
2154:
2041:{\displaystyle S\subseteq \Omega }
2035:
1954:
1918:
1883:{\displaystyle S\subseteq \Omega }
1877:
1755:
1644:{\displaystyle S\subseteq \Omega }
1638:
1557:
1535:{\displaystyle S\subseteq \Omega }
1529:
1424:
1349:
1154:
792:
574:
534:{\displaystyle X\subseteq \Omega }
528:
413:
274:
222:
186:
160:
125:
90:
14:
6561:
6511:
5856:. In Gonzalez, Teofilo F. (ed.).
5845:
5820:
5793:
5110:
4835:{\displaystyle g(S)=\min(f(S),c)}
4761:
4157:{\displaystyle 0\leq x_{i}\leq 1}
3820:{\displaystyle 0\leq x_{i}\leq 1}
3710:
3544:{\displaystyle 0\leq x_{i}\leq 1}
3253:{\displaystyle 0\leq x_{i}\leq 1}
1933:{\displaystyle f(S)=f(\Omega -S)}
277:
5908:
4433:
4409:
4385:
4368:
4272:
4185:
4060:
3935:
3848:
3723:
3565:
3447:
3283:
3156:
3075:{\displaystyle x\in \{0,1\}^{n}}
2638:of the submodular set function.
2338:is a submodular function, where
1680:is a submodular function, where
6300:
5997:
5952:
5737:
5018:independently with probability
4978:is chosen with each element in
1823:
626:{\displaystyle x_{1}\neq x_{2}}
5882:
5832:
5530:
5501:
5495:
5476:
5429:
5423:
5406:
5403:
5397:
5391:
5113:
5107:
5101:
5089:
5083:
5077:
5065:
5062:
5056:
5050:
4922:
4919:
4913:
4907:
4898:
4892:
4829:
4820:
4814:
4808:
4799:
4793:
4767:
4755:
4746:
4740:
4694:
4688:
4641:
4635:
4437:
4429:
4413:
4405:
4389:
4381:
4372:
4364:
4232:
4226:
4189:
4181:
4025:
4012:
3895:
3889:
3852:
3844:
3664:
3645:
3600:
3594:
3569:
3561:
3398:
3386:
3355:where the expectation is over
3340:
3337:
3314:
3304:
3298:
3287:
3279:
3120:
3114:
3105:
3092:
2999:
2990:
2977:
2698:
2690:
2664:
2614:{\displaystyle v\in \Omega -S}
2550:
2538:
2512:
2506:
2372:{\displaystyle I(S;\Omega -S)}
2366:
2348:
2325:
2307:
2298:
2292:
2166:{\displaystyle v\in \Omega -S}
2102:
2090:
2064:
2058:
1927:
1915:
1906:
1900:
1696:
1690:
1667:
1661:
1457:
1451:
1213:
1207:
1105:
1099:
1069:
1063:
1054:
1048:
896:
890:
841:
835:
764:
758:
749:
711:
702:
677:
668:
643:
499:
487:
478:
466:
457:
451:
442:
436:
378:
372:
363:
345:
336:
330:
321:
303:
130:
1:
6384:
5714:Related optimization problems
5661:approximation algorithm. The
5244:by including each element in
4473:
3126:{\displaystyle F(x^{S})=f(S)}
2383:
1075:{\displaystyle f(T)\leq f(S)}
78:
5928:10.1007/978-3-642-68874-4_10
5787:
5139:{\displaystyle \varnothing }
4928:{\displaystyle g(S)=h(f(S))}
4710:For any submodular function
3017:, that matches the value of
1835:
1031:{\displaystyle T\subseteq S}
254:{\displaystyle X\subseteq Y}
65:multi-document summarization
7:
5959:Vondrak, Jan (2008-05-17).
5761:
2930:{\displaystyle x_{i}^{S}=0}
2866:{\displaystyle x_{i}^{S}=1}
2750:{\displaystyle \{0,1\}^{n}}
2711:{\displaystyle |\Omega |=n}
2525:denote the number of edges
2077:denote the number of edges
1303:{\displaystyle w_{i}\geq 0}
983:
168:{\displaystyle 2^{\Omega }}
10:
6566:
6540:Combinatorial optimization
6441:Fujishige, Satoru (2005),
6425:Cambridge University Press
6396:Combinatorial Optimization
4730:, the function defined by
3431:is a submodular function.
2470:. For any set of vertices
2379:is the mutual information.
2022:. For any set of vertices
1336:is called budget additive.
1086:Linear (Modular) functions
6524:http://submodularity.org/
6520:has a longer bibliography
6010:SIAM Journal on Computing
4546:and non-negative numbers
2964:is a continuous function
2641:Formally, a set function
1197:Any function of the form
1193:Budget-additive functions
1089:Any function of the form
6545:Approximation algorithms
6481:Oxley, James G. (1992),
6274:Mathematical Programming
6196:J. Combin. Theory Ser. B
5860:. Chapman and Hall/CRC.
5706:approximation algorithm.
5663:maximum coverage problem
3368:{\displaystyle \lambda }
1434:{\displaystyle \Omega '}
41:approximation algorithms
6487:Oxford University Press
5973:10.1145/1374376.1374389
5614:local search algorithms
4991:{\displaystyle \Omega }
2556:{\displaystyle e=(u,v)}
2108:{\displaystyle e=(u,v)}
1329:{\displaystyle B\geq 0}
798:{\displaystyle \Omega }
192:{\displaystyle \Omega }
96:{\displaystyle \Omega }
61:automatic summarization
57:artificial intelligence
21:submodular set function
6463:Narayanan, H. (1997),
6209:10.1006/jctb.2000.1989
5700:
5655:
5560:. For this reason, an
5537:
5373:
5319:
5292:
5265:
5238:
5211:
5160:
5140:
5120:
5032:
5012:
4992:
4972:
4949:
4929:
4876:
4856:
4836:
4774:
4724:
4701:
4667:
4619:
4599:
4540:
4464:
4444:
4333:
4158:
4119:
4038:
3996:
3821:
3782:
3671:
3545:
3506:
3425:
3405:
3369:
3347:
3254:
3215:
3148:. Consider any vector
3127:
3076:
3031:
3011:
2958:
2931:
2893:
2892:{\displaystyle i\in S}
2867:
2829:
2777:
2757:, by associating each
2751:
2712:
2676:
2615:
2583:
2582:{\displaystyle u\in S}
2557:
2519:
2490:
2460:
2373:
2332:
2276:
2246:
2167:
2135:
2134:{\displaystyle u\in S}
2109:
2071:
2042:
2012:
1934:
1884:
1854:
1813:
1723:
1703:
1674:
1645:
1615:
1536:
1510:
1435:
1407:
1330:
1304:
1271:
1183:
1141:
1076:
1032:
1002:
969:
949:
929:
909:
908:{\displaystyle f(S)=0}
874:
854:
853:{\displaystyle f(S)=1}
819:
799:
771:
627:
587:
535:
506:
420:
385:
287:
255:
229:
193:
169:
142:
97:
6307:Williamson, David P.
6166:10.1145/502090.502096
5905:Fujishige (2005) p.22
5866:10.1201/9781351236423
5768:Supermodular function
5701:
5699:{\displaystyle 1-1/e}
5656:
5654:{\displaystyle 1-1/e}
5548:Optimization problems
5538:
5374:
5320:
5318:{\displaystyle p_{i}}
5293:
5291:{\displaystyle S_{i}}
5266:
5264:{\displaystyle A_{i}}
5239:
5237:{\displaystyle S_{i}}
5212:
5161:
5141:
5121:
5033:
5013:
4993:
4973:
4950:
4930:
4877:
4857:
4837:
4775:
4725:
4702:
4647:
4620:
4600:
4541:
4465:
4445:
4334:
4159:
4120:
4039:
3997:
3822:
3783:
3672:
3546:
3507:
3435:Multilinear extension
3426:
3406:
3370:
3348:
3255:
3216:
3128:
3077:
3032:
3012:
2959:
2932:
2894:
2868:
2830:
2783:with a binary vector
2778:
2752:
2713:
2677:
2616:
2584:
2558:
2520:
2491:
2466:be the vertices of a
2461:
2374:
2333:
2277:
2247:
2168:
2136:
2110:
2072:
2043:
2018:be the vertices of a
2013:
1935:
1885:
1855:
1814:
1724:
1704:
1675:
1646:
1616:
1537:
1511:
1436:
1408:
1331:
1305:
1272:
1184:
1142:
1077:
1033:
1003:
970:
950:
930:
910:
875:
855:
820:
800:
772:
628:
588:
536:
507:
421:
386:
288:
256:
230:
194:
170:
143:
98:
6392:Schrijver, Alexander
5922:. pp. 235–257.
5842:, §44, p. 766)
5731:welfare maximization
5676:
5631:
5584:time. Computing the
5562:optimization problem
5383:
5329:
5302:
5275:
5248:
5221:
5170:
5150:
5130:
5042:
5022:
5002:
4982:
4962:
4939:
4886:
4866:
4846:
4787:
4734:
4714:
4629:
4609:
4605:. Then the function
4550:
4491:
4454:
4351:
4168:
4129:
4056:
4052:Consider any vector
4037:{\displaystyle ^{n}}
4009:
3831:
3792:
3719:
3715:Consider any vector
3555:
3516:
3443:
3439:Consider any vector
3415:
3383:
3377:uniform distribution
3359:
3266:
3225:
3152:
3086:
3041:
3021:
2968:
2948:
2903:
2877:
2839:
2787:
2761:
2722:
2686:
2645:
2636:continuous extension
2593:
2567:
2529:
2518:{\displaystyle f(S)}
2500:
2474:
2399:
2342:
2286:
2260:
2185:
2145:
2119:
2081:
2070:{\displaystyle f(S)}
2052:
2026:
1951:
1894:
1868:
1844:
1752:
1731:Shannon's inequality
1713:
1702:{\displaystyle H(S)}
1684:
1673:{\displaystyle H(S)}
1655:
1629:
1554:
1520:
1445:
1420:
1346:
1314:
1281:
1201:
1151:
1093:
1042:
1016:
992:
959:
939:
919:
884:
864:
829:
809:
789:
637:
597:
545:
519:
430:
398:
297:
265:
239:
207:
183:
152:
111:
87:
5582:strongly-polynomial
5358:
5271:independently into
4485:linear combinations
4483:under non-negative
2920:
2856:
1189:then f is monotone.
49:electrical networks
37:diminishing returns
33:diminishing returns
25:submodular function
6286:10.1007/BF01588971
6131:10.1007/BF02579361
6086:10.1007/BF02579273
5696:
5651:
5533:
5433:
5369:
5338:
5325:. Furthermore let
5315:
5288:
5261:
5234:
5207:
5156:
5136:
5116:
5028:
5008:
4998:being included in
4988:
4968:
4945:
4925:
4872:
4852:
4832:
4770:
4720:
4697:
4615:
4595:
4536:
4460:
4440:
4329:
4288:
4247:
4212:
4154:
4115:
4034:
3992:
3951:
3910:
3875:
3817:
3778:
3667:
3644:
3618:
3590:
3541:
3502:
3421:
3401:
3365:
3343:
3250:
3211:
3123:
3072:
3027:
3007:
2954:
2927:
2906:
2889:
2863:
2842:
2825:
2773:
2747:
2708:
2672:
2611:
2579:
2553:
2515:
2486:
2456:
2369:
2328:
2272:
2242:
2177:Mutual information
2163:
2131:
2105:
2067:
2038:
2008:
1930:
1880:
1850:
1809:
1729:, a fact known as
1719:
1699:
1670:
1641:
1611:
1532:
1506:
1490:
1431:
1403:
1339:Coverage functions
1326:
1300:
1267:
1251:
1179:
1137:
1126:
1072:
1028:
998:
965:
945:
925:
905:
870:
850:
815:
795:
767:
623:
583:
531:
502:
416:
381:
283:
251:
225:
189:
165:
138:
93:
19:In mathematics, a
6270:Nemhauser, George
6022:10.1137/080733991
5982:978-1-60558-047-0
5937:978-3-642-68876-8
5610:greedy algorithms
5558:concave functions
5412:
5298:with probability
5159:{\displaystyle S}
5031:{\displaystyle p}
5011:{\displaystyle T}
4971:{\displaystyle T}
4948:{\displaystyle h}
4875:{\displaystyle f}
4855:{\displaystyle c}
4723:{\displaystyle f}
4618:{\displaystyle g}
4463:{\displaystyle f}
4279:
4238:
4203:
3942:
3901:
3866:
3629:
3603:
3575:
3424:{\displaystyle f}
3030:{\displaystyle f}
2957:{\displaystyle f}
1853:{\displaystyle f}
1722:{\displaystyle S}
1468:
1236:
1235:
1111:
1001:{\displaystyle f}
968:{\displaystyle T}
948:{\displaystyle S}
928:{\displaystyle S}
873:{\displaystyle S}
818:{\displaystyle f}
69:feature selection
23:(also known as a
6557:
6507:
6477:
6459:
6437:
6412:
6379:
6376:
6370:
6367:
6361:
6358:
6352:
6349:
6343:
6340:
6334:
6331:
6325:
6322:
6316:
6315:
6313:
6304:
6298:
6297:
6266:
6260:
6257:
6251:
6245:
6239:
6232:
6223:
6220:
6214:
6213:
6211:
6184:
6178:
6177:
6149:
6143:
6142:
6114:
6108:
6107:
6097:
6058:
6052:
6051:
6049:
6040:
6034:
6033:
6016:(6): 1740–1766.
6001:
5995:
5994:
5956:
5950:
5949:
5912:
5906:
5903:
5897:
5896:
5894:
5886:
5880:
5879:
5849:
5843:
5838:(Schrijver
5836:
5830:
5827:
5818:
5815:
5809:
5806:
5800:
5797:
5752:machine learning
5705:
5703:
5702:
5697:
5692:
5660:
5658:
5657:
5652:
5647:
5542:
5540:
5539:
5534:
5529:
5528:
5519:
5518:
5494:
5493:
5475:
5474:
5459:
5458:
5449:
5448:
5432:
5390:
5378:
5376:
5375:
5370:
5368:
5367:
5357:
5352:
5324:
5322:
5321:
5316:
5314:
5313:
5297:
5295:
5294:
5289:
5287:
5286:
5270:
5268:
5267:
5262:
5260:
5259:
5243:
5241:
5240:
5235:
5233:
5232:
5216:
5214:
5213:
5208:
5200:
5199:
5165:
5163:
5162:
5157:
5145:
5143:
5142:
5137:
5125:
5123:
5122:
5117:
5049:
5037:
5035:
5034:
5029:
5017:
5015:
5014:
5009:
4997:
4995:
4994:
4989:
4977:
4975:
4974:
4969:
4954:
4952:
4951:
4946:
4934:
4932:
4931:
4926:
4881:
4879:
4878:
4873:
4861:
4859:
4858:
4853:
4841:
4839:
4838:
4833:
4779:
4777:
4776:
4771:
4729:
4727:
4726:
4721:
4706:
4704:
4703:
4698:
4687:
4686:
4677:
4676:
4666:
4661:
4624:
4622:
4621:
4616:
4604:
4602:
4601:
4596:
4594:
4593:
4575:
4574:
4562:
4561:
4545:
4543:
4542:
4537:
4535:
4534:
4516:
4515:
4503:
4502:
4469:
4467:
4466:
4461:
4449:
4447:
4446:
4441:
4436:
4428:
4427:
4412:
4404:
4403:
4388:
4371:
4363:
4362:
4338:
4336:
4335:
4330:
4328:
4324:
4317:
4316:
4298:
4297:
4287:
4275:
4267:
4266:
4257:
4256:
4246:
4222:
4221:
4211:
4188:
4180:
4179:
4163:
4161:
4160:
4155:
4147:
4146:
4124:
4122:
4121:
4116:
4111:
4110:
4092:
4091:
4079:
4078:
4063:
4043:
4041:
4040:
4035:
4033:
4032:
4001:
3999:
3998:
3993:
3991:
3987:
3980:
3979:
3961:
3960:
3950:
3938:
3930:
3929:
3920:
3919:
3909:
3885:
3884:
3874:
3851:
3843:
3842:
3826:
3824:
3823:
3818:
3810:
3809:
3787:
3785:
3784:
3779:
3774:
3773:
3755:
3754:
3742:
3741:
3726:
3676:
3674:
3673:
3668:
3663:
3662:
3643:
3628:
3627:
3617:
3589:
3568:
3550:
3548:
3547:
3542:
3534:
3533:
3511:
3509:
3508:
3503:
3498:
3497:
3479:
3478:
3466:
3465:
3450:
3430:
3428:
3427:
3422:
3410:
3408:
3407:
3404:{\displaystyle }
3402:
3379:on the interval
3375:chosen from the
3374:
3372:
3371:
3366:
3352:
3350:
3349:
3344:
3327:
3326:
3317:
3297:
3286:
3278:
3277:
3259:
3257:
3256:
3251:
3243:
3242:
3220:
3218:
3217:
3212:
3207:
3206:
3188:
3187:
3175:
3174:
3159:
3140:Lovász extension
3132:
3130:
3129:
3124:
3104:
3103:
3081:
3079:
3078:
3073:
3071:
3070:
3036:
3034:
3033:
3028:
3016:
3014:
3013:
3008:
3006:
2998:
2997:
2963:
2961:
2960:
2955:
2936:
2934:
2933:
2928:
2919:
2914:
2898:
2896:
2895:
2890:
2872:
2870:
2869:
2864:
2855:
2850:
2834:
2832:
2831:
2826:
2824:
2823:
2799:
2798:
2782:
2780:
2779:
2774:
2756:
2754:
2753:
2748:
2746:
2745:
2717:
2715:
2714:
2709:
2701:
2693:
2681:
2679:
2678:
2673:
2671:
2663:
2662:
2620:
2618:
2617:
2612:
2588:
2586:
2585:
2580:
2562:
2560:
2559:
2554:
2524:
2522:
2521:
2516:
2495:
2493:
2492:
2487:
2465:
2463:
2462:
2457:
2452:
2451:
2433:
2432:
2420:
2419:
2378:
2376:
2375:
2370:
2337:
2335:
2334:
2329:
2281:
2279:
2278:
2273:
2254:random variables
2251:
2249:
2248:
2243:
2238:
2237:
2219:
2218:
2206:
2205:
2172:
2170:
2169:
2164:
2140:
2138:
2137:
2132:
2114:
2112:
2111:
2106:
2076:
2074:
2073:
2068:
2047:
2045:
2044:
2039:
2017:
2015:
2014:
2009:
2004:
2003:
1985:
1984:
1972:
1971:
1939:
1937:
1936:
1931:
1889:
1887:
1886:
1881:
1859:
1857:
1856:
1851:
1818:
1816:
1815:
1810:
1805:
1804:
1786:
1785:
1773:
1772:
1728:
1726:
1725:
1720:
1708:
1706:
1705:
1700:
1679:
1677:
1676:
1671:
1650:
1648:
1647:
1642:
1623:random variables
1620:
1618:
1617:
1612:
1607:
1606:
1588:
1587:
1575:
1574:
1541:
1539:
1538:
1533:
1515:
1513:
1512:
1507:
1505:
1501:
1500:
1499:
1489:
1482:
1481:
1440:
1438:
1437:
1432:
1430:
1412:
1410:
1409:
1404:
1399:
1398:
1380:
1379:
1367:
1366:
1335:
1333:
1332:
1327:
1309:
1307:
1306:
1301:
1293:
1292:
1276:
1274:
1273:
1268:
1266:
1262:
1261:
1260:
1250:
1233:
1188:
1186:
1185:
1180:
1172:
1171:
1146:
1144:
1143:
1138:
1136:
1135:
1125:
1081:
1079:
1078:
1073:
1037:
1035:
1034:
1029:
1007:
1005:
1004:
999:
974:
972:
971:
966:
954:
952:
951:
946:
934:
932:
931:
926:
914:
912:
911:
906:
879:
877:
876:
871:
859:
857:
856:
851:
824:
822:
821:
816:
804:
802:
801:
796:
776:
774:
773:
768:
745:
744:
732:
731:
698:
697:
664:
663:
632:
630:
629:
624:
622:
621:
609:
608:
592:
590:
589:
584:
570:
569:
557:
556:
540:
538:
537:
532:
511:
509:
508:
503:
425:
423:
422:
417:
390:
388:
387:
382:
292:
290:
289:
284:
260:
258:
257:
252:
234:
232:
231:
226:
198:
196:
195:
190:
174:
172:
171:
166:
164:
163:
147:
145:
144:
139:
137:
129:
128:
102:
100:
99:
94:
53:machine learning
6565:
6564:
6560:
6559:
6558:
6556:
6555:
6554:
6530:
6529:
6514:
6497:
6475:
6457:
6435:
6410:
6387:
6382:
6377:
6373:
6368:
6364:
6359:
6355:
6350:
6346:
6341:
6337:
6332:
6328:
6323:
6319:
6311:
6305:
6301:
6280:(14): 265–294.
6267:
6263:
6258:
6254:
6246:
6242:
6233:
6226:
6221:
6217:
6185:
6181:
6150:
6146:
6115:
6111:
6059:
6055:
6047:
6041:
6037:
6002:
5998:
5983:
5957:
5953:
5938:
5913:
5909:
5904:
5900:
5892:
5888:
5887:
5883:
5876:
5850:
5846:
5837:
5833:
5828:
5821:
5816:
5812:
5807:
5803:
5798:
5794:
5790:
5764:
5756:computer vision
5740:
5716:
5688:
5677:
5674:
5673:
5643:
5632:
5629:
5628:
5602:
5578:polynomial time
5570:
5550:
5524:
5520:
5508:
5504:
5489:
5485:
5464:
5460:
5454:
5450:
5438:
5434:
5416:
5386:
5384:
5381:
5380:
5363:
5359:
5353:
5342:
5330:
5327:
5326:
5309:
5305:
5303:
5300:
5299:
5282:
5278:
5276:
5273:
5272:
5255:
5251:
5249:
5246:
5245:
5228:
5224:
5222:
5219:
5218:
5195:
5191:
5171:
5168:
5167:
5151:
5148:
5147:
5131:
5128:
5127:
5045:
5043:
5040:
5039:
5023:
5020:
5019:
5003:
5000:
4999:
4983:
4980:
4979:
4963:
4960:
4959:
4940:
4937:
4936:
4887:
4884:
4883:
4867:
4864:
4863:
4847:
4844:
4843:
4788:
4785:
4784:
4735:
4732:
4731:
4715:
4712:
4711:
4682:
4678:
4672:
4668:
4662:
4651:
4630:
4627:
4626:
4610:
4607:
4606:
4589:
4585:
4570:
4566:
4557:
4553:
4551:
4548:
4547:
4530:
4526:
4511:
4507:
4498:
4494:
4492:
4489:
4488:
4476:
4470:is submodular.
4455:
4452:
4451:
4432:
4423:
4419:
4408:
4399:
4395:
4384:
4367:
4358:
4354:
4352:
4349:
4348:
4345:
4312:
4308:
4293:
4289:
4283:
4271:
4262:
4258:
4252:
4248:
4242:
4217:
4213:
4207:
4202:
4198:
4184:
4175:
4171:
4169:
4166:
4165:
4142:
4138:
4130:
4127:
4126:
4125:such that each
4106:
4102:
4087:
4083:
4074:
4070:
4059:
4057:
4054:
4053:
4050:
4048:Concave closure
4028:
4024:
4010:
4007:
4006:
3975:
3971:
3956:
3952:
3946:
3934:
3925:
3921:
3915:
3911:
3905:
3880:
3876:
3870:
3865:
3861:
3847:
3838:
3834:
3832:
3829:
3828:
3805:
3801:
3793:
3790:
3789:
3788:such that each
3769:
3765:
3750:
3746:
3737:
3733:
3722:
3720:
3717:
3716:
3713:
3685:
3658:
3654:
3633:
3623:
3619:
3607:
3579:
3564:
3556:
3553:
3552:
3529:
3525:
3517:
3514:
3513:
3512:such that each
3493:
3489:
3474:
3470:
3461:
3457:
3446:
3444:
3441:
3440:
3437:
3416:
3413:
3412:
3384:
3381:
3380:
3360:
3357:
3356:
3322:
3318:
3313:
3293:
3282:
3273:
3269:
3267:
3264:
3263:
3238:
3234:
3226:
3223:
3222:
3221:such that each
3202:
3198:
3183:
3179:
3170:
3166:
3155:
3153:
3150:
3149:
3142:
3099:
3095:
3087:
3084:
3083:
3066:
3062:
3042:
3039:
3038:
3022:
3019:
3018:
3002:
2993:
2989:
2969:
2966:
2965:
2949:
2946:
2945:
2915:
2910:
2904:
2901:
2900:
2878:
2875:
2874:
2851:
2846:
2840:
2837:
2836:
2819:
2815:
2794:
2790:
2788:
2785:
2784:
2762:
2759:
2758:
2741:
2737:
2723:
2720:
2719:
2697:
2689:
2687:
2684:
2683:
2667:
2658:
2654:
2646:
2643:
2642:
2628:
2594:
2591:
2590:
2568:
2565:
2564:
2530:
2527:
2526:
2501:
2498:
2497:
2475:
2472:
2471:
2447:
2443:
2428:
2424:
2415:
2411:
2400:
2397:
2396:
2386:
2343:
2340:
2339:
2287:
2284:
2283:
2261:
2258:
2257:
2256:. Then for any
2233:
2229:
2214:
2210:
2201:
2197:
2186:
2183:
2182:
2146:
2143:
2142:
2120:
2117:
2116:
2082:
2079:
2078:
2053:
2050:
2049:
2027:
2024:
2023:
1999:
1995:
1980:
1976:
1967:
1963:
1952:
1949:
1948:
1895:
1892:
1891:
1869:
1866:
1865:
1845:
1842:
1841:
1838:
1826:
1800:
1796:
1781:
1777:
1768:
1764:
1753:
1750:
1749:
1735:entropic vector
1714:
1711:
1710:
1685:
1682:
1681:
1656:
1653:
1652:
1630:
1627:
1626:
1625:. Then for any
1602:
1598:
1583:
1579:
1570:
1566:
1555:
1552:
1551:
1521:
1518:
1517:
1495:
1491:
1477:
1473:
1472:
1467:
1463:
1446:
1443:
1442:
1441:. The function
1423:
1421:
1418:
1417:
1394:
1390:
1375:
1371:
1362:
1358:
1347:
1344:
1343:
1315:
1312:
1311:
1288:
1284:
1282:
1279:
1278:
1256:
1252:
1240:
1226:
1222:
1202:
1199:
1198:
1167:
1163:
1152:
1149:
1148:
1131:
1127:
1115:
1094:
1091:
1090:
1043:
1040:
1039:
1017:
1014:
1013:
993:
990:
989:
988:A set function
986:
981:
960:
957:
956:
940:
937:
936:
920:
917:
916:
885:
882:
881:
865:
862:
861:
830:
827:
826:
810:
807:
806:
790:
787:
786:
740:
736:
727:
723:
693:
689:
659:
655:
638:
635:
634:
617:
613:
604:
600:
598:
595:
594:
565:
561:
552:
548:
546:
543:
542:
520:
517:
516:
431:
428:
427:
399:
396:
395:
298:
295:
294:
266:
263:
262:
240:
237:
236:
208:
205:
204:
184:
181:
180:
159:
155:
153:
150:
149:
133:
124:
120:
112:
109:
108:
88:
85:
84:
81:
73:active learning
35:). The natural
17:
12:
11:
5:
6563:
6553:
6552:
6550:Matroid theory
6547:
6542:
6528:
6527:
6521:
6513:
6512:External links
6510:
6509:
6508:
6495:
6483:Matroid theory
6478:
6473:
6460:
6455:
6438:
6433:
6413:
6408:
6386:
6383:
6381:
6380:
6371:
6362:
6353:
6344:
6335:
6326:
6317:
6299:
6261:
6252:
6240:
6224:
6215:
6202:(2): 346–355.
6179:
6160:(4): 761–777.
6144:
6125:(3): 185–192.
6109:
6080:(2): 169–197.
6053:
6043:Vondrák, Jan.
6035:
5996:
5981:
5951:
5936:
5907:
5898:
5881:
5874:
5844:
5831:
5819:
5810:
5801:
5791:
5789:
5786:
5785:
5784:
5779:
5770:
5763:
5760:
5739:
5736:
5735:
5734:
5727:
5723:
5715:
5712:
5708:
5707:
5695:
5691:
5687:
5684:
5681:
5666:
5650:
5646:
5642:
5639:
5636:
5625:
5601:
5598:
5597:
5596:
5589:
5580:, and even in
5569:
5566:
5549:
5546:
5545:
5544:
5532:
5527:
5523:
5517:
5514:
5511:
5507:
5503:
5500:
5497:
5492:
5488:
5484:
5481:
5478:
5473:
5470:
5467:
5463:
5457:
5453:
5447:
5444:
5441:
5437:
5431:
5428:
5425:
5422:
5419:
5415:
5411:
5408:
5405:
5402:
5399:
5396:
5393:
5389:
5366:
5362:
5356:
5351:
5348:
5345:
5341:
5337:
5334:
5312:
5308:
5285:
5281:
5258:
5254:
5231:
5227:
5206:
5203:
5198:
5194:
5190:
5187:
5184:
5181:
5178:
5175:
5155:
5135:
5115:
5112:
5109:
5106:
5103:
5100:
5097:
5094:
5091:
5088:
5085:
5082:
5079:
5076:
5073:
5070:
5067:
5064:
5061:
5058:
5055:
5052:
5048:
5027:
5007:
4987:
4967:
4956:
4944:
4924:
4921:
4918:
4915:
4912:
4909:
4906:
4903:
4900:
4897:
4894:
4891:
4871:
4851:
4831:
4828:
4825:
4822:
4819:
4816:
4813:
4810:
4807:
4804:
4801:
4798:
4795:
4792:
4781:
4780:is submodular.
4769:
4766:
4763:
4760:
4757:
4754:
4751:
4748:
4745:
4742:
4739:
4719:
4708:
4707:is submodular.
4696:
4693:
4690:
4685:
4681:
4675:
4671:
4665:
4660:
4657:
4654:
4650:
4646:
4643:
4640:
4637:
4634:
4614:
4592:
4588:
4584:
4581:
4578:
4573:
4569:
4565:
4560:
4556:
4533:
4529:
4525:
4522:
4519:
4514:
4510:
4506:
4501:
4497:
4475:
4472:
4459:
4439:
4435:
4431:
4426:
4422:
4418:
4415:
4411:
4407:
4402:
4398:
4394:
4391:
4387:
4383:
4380:
4377:
4374:
4370:
4366:
4361:
4357:
4344:
4341:
4327:
4323:
4320:
4315:
4311:
4307:
4304:
4301:
4296:
4292:
4286:
4282:
4278:
4274:
4270:
4265:
4261:
4255:
4251:
4245:
4241:
4237:
4234:
4231:
4228:
4225:
4220:
4216:
4210:
4206:
4201:
4197:
4194:
4191:
4187:
4183:
4178:
4174:
4153:
4150:
4145:
4141:
4137:
4134:
4114:
4109:
4105:
4101:
4098:
4095:
4090:
4086:
4082:
4077:
4073:
4069:
4066:
4062:
4049:
4046:
4031:
4027:
4023:
4020:
4017:
4014:
3990:
3986:
3983:
3978:
3974:
3970:
3967:
3964:
3959:
3955:
3949:
3945:
3941:
3937:
3933:
3928:
3924:
3918:
3914:
3908:
3904:
3900:
3897:
3894:
3891:
3888:
3883:
3879:
3873:
3869:
3864:
3860:
3857:
3854:
3850:
3846:
3841:
3837:
3816:
3813:
3808:
3804:
3800:
3797:
3777:
3772:
3768:
3764:
3761:
3758:
3753:
3749:
3745:
3740:
3736:
3732:
3729:
3725:
3712:
3711:Convex closure
3709:
3683:
3666:
3661:
3657:
3653:
3650:
3647:
3642:
3639:
3636:
3632:
3626:
3622:
3616:
3613:
3610:
3606:
3602:
3599:
3596:
3593:
3588:
3585:
3582:
3578:
3574:
3571:
3567:
3563:
3560:
3540:
3537:
3532:
3528:
3524:
3521:
3501:
3496:
3492:
3488:
3485:
3482:
3477:
3473:
3469:
3464:
3460:
3456:
3453:
3449:
3436:
3433:
3420:
3400:
3397:
3394:
3391:
3388:
3364:
3342:
3339:
3336:
3333:
3330:
3325:
3321:
3316:
3312:
3309:
3306:
3303:
3300:
3296:
3292:
3289:
3285:
3281:
3276:
3272:
3249:
3246:
3241:
3237:
3233:
3230:
3210:
3205:
3201:
3197:
3194:
3191:
3186:
3182:
3178:
3173:
3169:
3165:
3162:
3158:
3141:
3138:
3122:
3119:
3116:
3113:
3110:
3107:
3102:
3098:
3094:
3091:
3069:
3065:
3061:
3058:
3055:
3052:
3049:
3046:
3026:
3005:
3001:
2996:
2992:
2988:
2985:
2982:
2979:
2976:
2973:
2953:
2926:
2923:
2918:
2913:
2909:
2888:
2885:
2882:
2862:
2859:
2854:
2849:
2845:
2822:
2818:
2814:
2811:
2808:
2805:
2802:
2797:
2793:
2772:
2769:
2766:
2744:
2740:
2736:
2733:
2730:
2727:
2707:
2704:
2700:
2696:
2692:
2670:
2666:
2661:
2657:
2653:
2650:
2627:
2624:
2623:
2622:
2610:
2607:
2604:
2601:
2598:
2578:
2575:
2572:
2552:
2549:
2546:
2543:
2540:
2537:
2534:
2514:
2511:
2508:
2505:
2485:
2482:
2479:
2468:directed graph
2455:
2450:
2446:
2442:
2439:
2436:
2431:
2427:
2423:
2418:
2414:
2410:
2407:
2404:
2393:
2385:
2382:
2381:
2380:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2327:
2324:
2321:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2271:
2268:
2265:
2241:
2236:
2232:
2228:
2225:
2222:
2217:
2213:
2209:
2204:
2200:
2196:
2193:
2190:
2179:
2174:
2162:
2159:
2156:
2153:
2150:
2130:
2127:
2124:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2066:
2063:
2060:
2057:
2037:
2034:
2031:
2007:
2002:
1998:
1994:
1991:
1988:
1983:
1979:
1975:
1970:
1966:
1962:
1959:
1956:
1945:
1929:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1905:
1902:
1899:
1879:
1876:
1873:
1849:
1837:
1834:
1825:
1822:
1821:
1820:
1808:
1803:
1799:
1795:
1792:
1789:
1784:
1780:
1776:
1771:
1767:
1763:
1760:
1757:
1746:
1744:rank functions
1738:
1718:
1698:
1695:
1692:
1689:
1669:
1666:
1663:
1660:
1640:
1637:
1634:
1610:
1605:
1601:
1597:
1594:
1591:
1586:
1582:
1578:
1573:
1569:
1565:
1562:
1559:
1548:
1543:
1531:
1528:
1525:
1504:
1498:
1494:
1488:
1485:
1480:
1476:
1471:
1466:
1462:
1459:
1456:
1453:
1450:
1429:
1426:
1402:
1397:
1393:
1389:
1386:
1383:
1378:
1374:
1370:
1365:
1361:
1357:
1354:
1351:
1340:
1337:
1325:
1322:
1319:
1299:
1296:
1291:
1287:
1265:
1259:
1255:
1249:
1246:
1243:
1239:
1232:
1229:
1225:
1221:
1218:
1215:
1212:
1209:
1206:
1195:
1190:
1178:
1175:
1170:
1166:
1162:
1159:
1156:
1134:
1130:
1124:
1121:
1118:
1114:
1110:
1107:
1104:
1101:
1098:
1087:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1027:
1024:
1021:
997:
985:
982:
980:
977:
964:
944:
924:
904:
901:
898:
895:
892:
889:
880:is finite and
869:
849:
846:
843:
840:
837:
834:
814:
794:
779:
778:
766:
763:
760:
757:
754:
751:
748:
743:
739:
735:
730:
726:
722:
719:
716:
713:
710:
707:
704:
701:
696:
692:
688:
685:
682:
679:
676:
673:
670:
667:
662:
658:
654:
651:
648:
645:
642:
620:
616:
612:
607:
603:
582:
579:
576:
573:
568:
564:
560:
555:
551:
530:
527:
524:
513:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
415:
412:
409:
406:
403:
392:
380:
377:
374:
371:
368:
365:
362:
359:
356:
353:
350:
347:
344:
341:
338:
335:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
282:
279:
276:
273:
270:
250:
247:
244:
224:
221:
218:
215:
212:
188:
162:
158:
136:
132:
127:
123:
119:
116:
92:
80:
77:
15:
9:
6:
4:
3:
2:
6562:
6551:
6548:
6546:
6543:
6541:
6538:
6537:
6535:
6525:
6522:
6519:
6516:
6515:
6506:
6502:
6498:
6496:0-19-853563-5
6492:
6488:
6484:
6479:
6476:
6474:0-444-82523-1
6470:
6466:
6461:
6458:
6456:0-444-52086-4
6452:
6448:
6444:
6439:
6436:
6434:0-521-01012-8
6430:
6426:
6422:
6418:
6414:
6411:
6409:3-540-44389-4
6405:
6401:
6397:
6393:
6389:
6388:
6375:
6366:
6357:
6348:
6339:
6330:
6321:
6310:
6303:
6295:
6291:
6287:
6283:
6279:
6275:
6271:
6265:
6256:
6249:
6244:
6237:
6231:
6229:
6219:
6210:
6205:
6201:
6197:
6193:
6189:
6188:Schrijver, A.
6183:
6175:
6171:
6167:
6163:
6159:
6155:
6148:
6140:
6136:
6132:
6128:
6124:
6120:
6119:Combinatorica
6113:
6105:
6101:
6096:
6091:
6087:
6083:
6079:
6075:
6074:Combinatorica
6071:
6070:Schrijver, A.
6067:
6063:
6062:Grötschel, M.
6057:
6046:
6039:
6031:
6027:
6023:
6019:
6015:
6011:
6007:
6000:
5992:
5988:
5984:
5978:
5974:
5970:
5966:
5962:
5955:
5947:
5943:
5939:
5933:
5929:
5925:
5921:
5917:
5911:
5902:
5891:
5885:
5877:
5875:9781351236423
5871:
5867:
5863:
5859:
5855:
5848:
5841:
5835:
5826:
5824:
5814:
5805:
5796:
5792:
5783:
5780:
5778:
5774:
5771:
5769:
5766:
5765:
5759:
5757:
5753:
5749:
5745:
5732:
5728:
5724:
5721:
5720:
5719:
5711:
5693:
5689:
5685:
5682:
5679:
5671:
5667:
5664:
5648:
5644:
5640:
5637:
5634:
5626:
5623:
5619:
5618:
5617:
5615:
5611:
5607:
5594:
5590:
5587:
5583:
5579:
5575:
5574:
5573:
5565:
5563:
5559:
5555:
5525:
5521:
5515:
5512:
5509:
5505:
5498:
5490:
5486:
5482:
5479:
5471:
5468:
5465:
5455:
5451:
5445:
5442:
5439:
5426:
5420:
5417:
5413:
5409:
5400:
5394:
5364:
5360:
5354:
5349:
5346:
5343:
5339:
5335:
5332:
5310:
5306:
5283:
5279:
5256:
5252:
5229:
5225:
5201:
5196:
5192:
5188:
5185:
5182:
5179:
5176:
5173:
5153:
5133:
5104:
5098:
5095:
5092:
5086:
5074:
5071:
5068:
5059:
5053:
5025:
5005:
4965:
4957:
4942:
4916:
4910:
4904:
4901:
4895:
4889:
4869:
4849:
4826:
4823:
4817:
4811:
4802:
4796:
4790:
4783:The function
4782:
4764:
4752:
4749:
4743:
4737:
4717:
4709:
4691:
4683:
4679:
4673:
4669:
4663:
4658:
4655:
4652:
4648:
4644:
4638:
4632:
4612:
4590:
4586:
4582:
4579:
4576:
4571:
4567:
4563:
4558:
4554:
4531:
4527:
4523:
4520:
4517:
4512:
4508:
4504:
4499:
4495:
4486:
4482:
4478:
4477:
4471:
4457:
4424:
4420:
4416:
4400:
4396:
4392:
4378:
4375:
4359:
4355:
4340:
4325:
4321:
4318:
4313:
4309:
4305:
4302:
4299:
4294:
4290:
4284:
4280:
4276:
4268:
4263:
4259:
4253:
4249:
4243:
4239:
4235:
4229:
4223:
4218:
4214:
4208:
4204:
4199:
4192:
4176:
4172:
4151:
4148:
4143:
4139:
4135:
4132:
4107:
4103:
4099:
4096:
4093:
4088:
4084:
4080:
4075:
4071:
4064:
4045:
4029:
4021:
4018:
4015:
4003:
3988:
3984:
3981:
3976:
3972:
3968:
3965:
3962:
3957:
3953:
3947:
3943:
3939:
3931:
3926:
3922:
3916:
3912:
3906:
3902:
3898:
3892:
3886:
3881:
3877:
3871:
3867:
3862:
3855:
3839:
3835:
3814:
3811:
3806:
3802:
3798:
3795:
3770:
3766:
3762:
3759:
3756:
3751:
3747:
3743:
3738:
3734:
3727:
3708:
3706:
3702:
3698:
3694:
3690:
3686:
3680:Intuitively,
3678:
3659:
3655:
3651:
3648:
3640:
3637:
3634:
3630:
3624:
3620:
3614:
3611:
3608:
3604:
3597:
3591:
3583:
3580:
3576:
3572:
3558:
3538:
3535:
3530:
3526:
3522:
3519:
3494:
3490:
3486:
3483:
3480:
3475:
3471:
3467:
3462:
3458:
3451:
3432:
3418:
3395:
3392:
3389:
3378:
3362:
3353:
3331:
3328:
3323:
3319:
3310:
3301:
3290:
3274:
3270:
3261:
3247:
3244:
3239:
3235:
3231:
3228:
3203:
3199:
3195:
3192:
3189:
3184:
3180:
3176:
3171:
3167:
3160:
3147:
3146:László Lovász
3137:
3134:
3117:
3111:
3108:
3100:
3096:
3089:
3067:
3059:
3056:
3053:
3047:
3044:
3024:
2994:
2986:
2983:
2980:
2974:
2971:
2951:
2943:
2942:
2937:otherwise. A
2924:
2921:
2916:
2911:
2907:
2886:
2883:
2880:
2860:
2857:
2852:
2847:
2843:
2820:
2812:
2809:
2806:
2800:
2795:
2791:
2767:
2764:
2742:
2734:
2731:
2728:
2705:
2702:
2655:
2651:
2648:
2639:
2637:
2633:
2608:
2605:
2599:
2596:
2576:
2573:
2570:
2547:
2544:
2541:
2535:
2532:
2509:
2503:
2480:
2477:
2469:
2448:
2444:
2440:
2437:
2434:
2429:
2425:
2421:
2416:
2412:
2405:
2394:
2392:Directed cuts
2391:
2390:
2389:
2363:
2360:
2354:
2351:
2345:
2322:
2319:
2313:
2310:
2304:
2301:
2295:
2289:
2282:we have that
2266:
2263:
2255:
2234:
2230:
2226:
2223:
2220:
2215:
2211:
2207:
2202:
2198:
2191:
2180:
2178:
2175:
2160:
2157:
2151:
2148:
2128:
2125:
2122:
2099:
2096:
2093:
2087:
2084:
2061:
2055:
2032:
2029:
2021:
2000:
1996:
1992:
1989:
1986:
1981:
1977:
1973:
1968:
1964:
1957:
1946:
1943:
1942:
1941:
1924:
1921:
1912:
1909:
1903:
1897:
1890:we have that
1874:
1871:
1864:if for every
1863:
1847:
1833:
1831:
1801:
1797:
1793:
1790:
1787:
1782:
1778:
1774:
1769:
1765:
1758:
1747:
1745:
1742:
1739:
1736:
1732:
1716:
1693:
1687:
1664:
1658:
1651:we have that
1635:
1632:
1624:
1603:
1599:
1595:
1592:
1589:
1584:
1580:
1576:
1571:
1567:
1560:
1549:
1547:
1544:
1526:
1523:
1502:
1496:
1492:
1486:
1483:
1478:
1474:
1469:
1464:
1460:
1454:
1448:
1427:
1416:
1395:
1391:
1387:
1384:
1381:
1376:
1372:
1368:
1363:
1359:
1352:
1341:
1338:
1323:
1320:
1317:
1297:
1294:
1289:
1285:
1263:
1257:
1253:
1247:
1244:
1241:
1237:
1230:
1227:
1223:
1216:
1210:
1204:
1196:
1194:
1191:
1176:
1173:
1168:
1164:
1160:
1157:
1132:
1128:
1122:
1119:
1116:
1112:
1108:
1102:
1096:
1088:
1085:
1084:
1083:
1066:
1060:
1057:
1051:
1045:
1038:we have that
1025:
1022:
1019:
1012:if for every
1011:
995:
976:
962:
942:
922:
902:
899:
893:
887:
867:
847:
844:
838:
832:
812:
784:
761:
755:
752:
741:
737:
733:
728:
724:
717:
714:
708:
705:
694:
690:
683:
680:
674:
671:
660:
656:
649:
646:
640:
633:we have that
618:
614:
610:
605:
601:
580:
571:
566:
562:
558:
553:
549:
525:
522:
514:
496:
493:
490:
484:
481:
475:
472:
469:
463:
460:
454:
448:
445:
439:
433:
426:we have that
410:
407:
404:
401:
393:
375:
369:
366:
357:
351:
348:
342:
339:
333:
327:
324:
315:
309:
306:
300:
293:we have that
280:
271:
268:
248:
245:
242:
219:
216:
213:
210:
202:
201:
200:
178:
156:
121:
117:
114:
106:
76:
74:
70:
66:
62:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
6482:
6467:, Elsevier,
6464:
6442:
6420:
6395:
6374:
6365:
6356:
6347:
6338:
6329:
6320:
6302:
6277:
6273:
6264:
6255:
6243:
6218:
6199:
6195:
6182:
6157:
6153:
6147:
6122:
6118:
6112:
6095:10068/182482
6077:
6073:
6056:
6038:
6013:
6009:
5999:
5964:
5954:
5919:
5910:
5901:
5884:
5857:
5847:
5834:
5813:
5804:
5795:
5741:
5738:Applications
5717:
5709:
5603:
5571:
5551:
4346:
4051:
4004:
3714:
3704:
3700:
3696:
3692:
3688:
3681:
3679:
3438:
3354:
3262:
3143:
3135:
2938:
2640:
2635:
2631:
2629:
2387:
2252:be a set of
1861:
1839:
1830:non-monotone
1829:
1827:
1824:Non-monotone
1621:be a set of
1009:
987:
780:
175:denotes the
103:is a finite
82:
59:, including
29:set function
24:
20:
18:
5777:Polymatroid
5748:game theory
5726:guarantees.
5622:maximum cut
5586:minimum cut
4625:defined by
2939:continuous
825:defined by
783:subadditive
45:game theory
6534:Categories
6505:0784.05002
6385:References
6236:S. Jegelka
6066:Lovasz, L.
5916:Lovász, L.
5217:construct
4474:Properties
2835:such that
2632:fractional
2563:such that
2384:Asymmetric
2115:such that
1944:Graph cuts
1860:is called
1415:ground set
593:such that
515:For every
394:For every
261:and every
203:For every
79:Definition
6294:206800425
6234:R. Iyer,
6030:0097-5397
5946:117358746
5788:Citations
5744:economics
5683:−
5638:−
5513:∈
5506:∪
5483:−
5469:∉
5462:Π
5443:∈
5436:Π
5421:⊆
5414:∑
5410:≥
5340:∪
5205:Ω
5202:⊆
5183:≤
5177:≤
5134:∅
5111:∅
5096:−
5081:Ω
5069:≥
4986:Ω
4762:∖
4759:Ω
4670:α
4649:∑
4587:α
4580:…
4568:α
4555:α
4521:…
4401:−
4393:≥
4376:≥
4319:≥
4310:α
4291:α
4281:∑
4250:α
4240:∑
4215:α
4205:∑
4149:≤
4136:≤
4097:…
3982:≥
3973:α
3954:α
3944:∑
3913:α
3903:∑
3878:α
3868:∑
3840:−
3812:≤
3799:≤
3760:…
3652:−
3638:∉
3631:∏
3612:∈
3605:∏
3587:Ω
3584:⊆
3577:∑
3536:≤
3523:≤
3484:…
3363:λ
3332:λ
3329:≥
3245:≤
3232:≤
3193:…
3048:∈
3000:→
2941:extension
2884:∈
2801:∈
2771:Ω
2768:⊆
2695:Ω
2665:→
2660:Ω
2606:−
2603:Ω
2600:∈
2574:∈
2484:Ω
2481:⊆
2438:…
2403:Ω
2361:−
2358:Ω
2320:−
2317:Ω
2270:Ω
2267:⊆
2224:…
2189:Ω
2158:−
2155:Ω
2152:∈
2126:∈
2036:Ω
2033:⊆
1990:…
1955:Ω
1922:−
1919:Ω
1878:Ω
1875:⊆
1862:symmetric
1836:Symmetric
1791:…
1756:Ω
1639:Ω
1636:⊆
1593:…
1558:Ω
1530:Ω
1527:⊆
1484:∈
1470:⋃
1425:Ω
1385:…
1350:Ω
1321:≥
1295:≥
1277:for each
1245:∈
1238:∑
1174:≥
1155:∀
1120:∈
1113:∑
1058:≤
1023:⊆
793:Ω
718:∪
706:≥
684:∪
650:∪
611:≠
578:∖
575:Ω
572:∈
529:Ω
526:⊆
494:∩
473:∪
461:≥
414:Ω
411:⊆
367:−
352:∪
340:≥
325:−
310:∪
278:∖
275:Ω
272:∈
246:⊆
223:Ω
220:⊆
187:Ω
177:power set
161:Ω
131:→
126:Ω
91:Ω
6447:Elsevier
6419:(2004),
6417:Lee, Jon
6400:Springer
6394:(2003),
6248:U. Feige
6190:(2000).
6139:33192360
6104:43787103
5762:See also
4842:, where
1428:′
1010:monotone
984:Monotone
148:, where
5773:Matroid
5670:matroid
5606:NP-hard
5593:NP-hard
3082:, i.e.
1741:Matroid
1546:Entropy
27:) is a
6503:
6493:
6471:
6453:
6431:
6406:
6292:
6174:888513
6172:
6154:J. ACM
6137:
6102:
6028:
5991:170510
5989:
5979:
5944:
5934:
5895:. cmu.
5872:
5554:convex
5126:where
4481:closed
2899:, and
1234:
6312:(PDF)
6290:S2CID
6170:S2CID
6135:S2CID
6100:S2CID
6048:(PDF)
5987:S2CID
5942:S2CID
5893:(PDF)
4450:when
2873:when
2682:with
2020:graph
235:with
6491:ISBN
6469:ISBN
6451:ISBN
6429:ISBN
6404:ISBN
6026:ISSN
5977:ISBN
5932:ISBN
5870:ISBN
5840:2003
5754:and
5556:and
2589:and
2496:let
2395:Let
2181:Let
2141:and
2048:let
1947:Let
1748:Let
1550:Let
1516:for
1342:Let
1310:and
955:and
541:and
55:and
6501:Zbl
6282:doi
6204:doi
6162:doi
6127:doi
6090:hdl
6082:doi
6018:doi
5969:doi
5924:doi
5862:doi
5612:or
4806:min
4196:max
3859:min
3037:on
2944:of
1220:min
1008:is
915:if
860:if
179:of
105:set
83:If
6536::
6499:,
6489:,
6449:,
6445:,
6427:,
6423:,
6402:,
6398:,
6288:.
6278:14
6276:.
6227:^
6200:80
6198:.
6194:.
6168:.
6158:48
6156:.
6133:.
6121:.
6098:.
6088:.
6076:.
6068:;
6064:;
6024:.
6014:40
6012:.
6008:.
5985:.
5975:.
5963:.
5940:.
5930:.
5868:.
5822:^
5775:,
5750:,
5746:,
5733:).
5616:.
4339:.
4044:.
4002:.
3677:.
3133:.
1832:.
71:,
67:,
63:,
43:,
6314:.
6296:.
6284::
6212:.
6206::
6176:.
6164::
6141:.
6129::
6123:5
6106:.
6092::
6084::
6078:1
6050:.
6032:.
6020::
5993:.
5971::
5948:.
5926::
5878:.
5864::
5694:e
5690:/
5686:1
5680:1
5649:e
5645:/
5641:1
5635:1
5543:.
5531:)
5526:i
5522:A
5516:R
5510:i
5502:(
5499:f
5496:)
5491:i
5487:p
5480:1
5477:(
5472:R
5466:i
5456:i
5452:p
5446:R
5440:i
5430:]
5427:l
5424:[
5418:R
5407:]
5404:)
5401:S
5398:(
5395:f
5392:[
5388:E
5365:i
5361:S
5355:l
5350:1
5347:=
5344:i
5336:=
5333:S
5311:i
5307:p
5284:i
5280:S
5257:i
5253:A
5230:i
5226:S
5197:i
5193:A
5189:,
5186:l
5180:i
5174:1
5154:S
5114:)
5108:(
5105:f
5102:)
5099:p
5093:1
5090:(
5087:+
5084:)
5078:(
5075:f
5072:p
5066:]
5063:)
5060:T
5057:(
5054:f
5051:[
5047:E
5026:p
5006:T
4966:T
4955:.
4943:h
4923:)
4920:)
4917:S
4914:(
4911:f
4908:(
4905:h
4902:=
4899:)
4896:S
4893:(
4890:g
4870:f
4850:c
4830:)
4827:c
4824:,
4821:)
4818:S
4815:(
4812:f
4809:(
4803:=
4800:)
4797:S
4794:(
4791:g
4768:)
4765:S
4756:(
4753:f
4750:=
4747:)
4744:S
4741:(
4738:g
4718:f
4695:)
4692:S
4689:(
4684:i
4680:f
4674:i
4664:k
4659:1
4656:=
4653:i
4645:=
4642:)
4639:S
4636:(
4633:g
4613:g
4591:k
4583:,
4577:,
4572:2
4564:,
4559:1
4532:k
4528:f
4524:,
4518:,
4513:2
4509:f
4505:,
4500:1
4496:f
4458:f
4438:)
4434:x
4430:(
4425:L
4421:f
4417:=
4414:)
4410:x
4406:(
4397:f
4390:)
4386:x
4382:(
4379:F
4373:)
4369:x
4365:(
4360:+
4356:f
4326:)
4322:0
4314:S
4306:,
4303:1
4300:=
4295:S
4285:S
4277:,
4273:x
4269:=
4264:S
4260:1
4254:S
4244:S
4236::
4233:)
4230:S
4227:(
4224:f
4219:S
4209:S
4200:(
4193:=
4190:)
4186:x
4182:(
4177:+
4173:f
4152:1
4144:i
4140:x
4133:0
4113:}
4108:n
4104:x
4100:,
4094:,
4089:2
4085:x
4081:,
4076:1
4072:x
4068:{
4065:=
4061:x
4030:n
4026:]
4022:1
4019:,
4016:0
4013:[
3989:)
3985:0
3977:S
3969:,
3966:1
3963:=
3958:S
3948:S
3940:,
3936:x
3932:=
3927:S
3923:1
3917:S
3907:S
3899::
3896:)
3893:S
3890:(
3887:f
3882:S
3872:S
3863:(
3856:=
3853:)
3849:x
3845:(
3836:f
3815:1
3807:i
3803:x
3796:0
3776:}
3771:n
3767:x
3763:,
3757:,
3752:2
3748:x
3744:,
3739:1
3735:x
3731:{
3728:=
3724:x
3705:i
3701:f
3697:S
3693:S
3689:i
3684:i
3682:x
3665:)
3660:i
3656:x
3649:1
3646:(
3641:S
3635:i
3625:i
3621:x
3615:S
3609:i
3601:)
3598:S
3595:(
3592:f
3581:S
3573:=
3570:)
3566:x
3562:(
3559:F
3539:1
3531:i
3527:x
3520:0
3500:}
3495:n
3491:x
3487:,
3481:,
3476:2
3472:x
3468:,
3463:1
3459:x
3455:{
3452:=
3448:x
3419:f
3399:]
3396:1
3393:,
3390:0
3387:[
3341:)
3338:)
3335:}
3324:i
3320:x
3315:|
3311:i
3308:{
3305:(
3302:f
3299:(
3295:E
3291:=
3288:)
3284:x
3280:(
3275:L
3271:f
3248:1
3240:i
3236:x
3229:0
3209:}
3204:n
3200:x
3196:,
3190:,
3185:2
3181:x
3177:,
3172:1
3168:x
3164:{
3161:=
3157:x
3121:)
3118:S
3115:(
3112:f
3109:=
3106:)
3101:S
3097:x
3093:(
3090:F
3068:n
3064:}
3060:1
3057:,
3054:0
3051:{
3045:x
3025:f
3004:R
2995:n
2991:]
2987:1
2984:,
2981:0
2978:[
2975::
2972:F
2952:f
2925:0
2922:=
2917:S
2912:i
2908:x
2887:S
2881:i
2861:1
2858:=
2853:S
2848:i
2844:x
2821:n
2817:}
2813:1
2810:,
2807:0
2804:{
2796:S
2792:x
2765:S
2743:n
2739:}
2735:1
2732:,
2729:0
2726:{
2706:n
2703:=
2699:|
2691:|
2669:R
2656:2
2652::
2649:f
2609:S
2597:v
2577:S
2571:u
2551:)
2548:v
2545:,
2542:u
2539:(
2536:=
2533:e
2513:)
2510:S
2507:(
2504:f
2478:S
2454:}
2449:n
2445:v
2441:,
2435:,
2430:2
2426:v
2422:,
2417:1
2413:v
2409:{
2406:=
2367:)
2364:S
2355:;
2352:S
2349:(
2346:I
2326:)
2323:S
2314:;
2311:S
2308:(
2305:I
2302:=
2299:)
2296:S
2293:(
2290:f
2264:S
2240:}
2235:n
2231:X
2227:,
2221:,
2216:2
2212:X
2208:,
2203:1
2199:X
2195:{
2192:=
2161:S
2149:v
2129:S
2123:u
2103:)
2100:v
2097:,
2094:u
2091:(
2088:=
2085:e
2065:)
2062:S
2059:(
2056:f
2030:S
2006:}
2001:n
1997:v
1993:,
1987:,
1982:2
1978:v
1974:,
1969:1
1965:v
1961:{
1958:=
1928:)
1925:S
1916:(
1913:f
1910:=
1907:)
1904:S
1901:(
1898:f
1872:S
1848:f
1807:}
1802:n
1798:e
1794:,
1788:,
1783:2
1779:e
1775:,
1770:1
1766:e
1762:{
1759:=
1737:.
1717:S
1697:)
1694:S
1691:(
1688:H
1668:)
1665:S
1662:(
1659:H
1633:S
1609:}
1604:n
1600:X
1596:,
1590:,
1585:2
1581:X
1577:,
1572:1
1568:X
1564:{
1561:=
1524:S
1503:|
1497:i
1493:E
1487:S
1479:i
1475:E
1465:|
1461:=
1458:)
1455:S
1452:(
1449:f
1401:}
1396:n
1392:E
1388:,
1382:,
1377:2
1373:E
1369:,
1364:1
1360:E
1356:{
1353:=
1324:0
1318:B
1298:0
1290:i
1286:w
1264:}
1258:i
1254:w
1248:S
1242:i
1231:,
1228:B
1224:{
1217:=
1214:)
1211:S
1208:(
1205:f
1177:0
1169:i
1165:w
1161:,
1158:i
1133:i
1129:w
1123:S
1117:i
1109:=
1106:)
1103:S
1100:(
1097:f
1070:)
1067:S
1064:(
1061:f
1055:)
1052:T
1049:(
1046:f
1026:S
1020:T
996:f
963:T
943:S
923:S
903:0
900:=
897:)
894:S
891:(
888:f
868:S
848:1
845:=
842:)
839:S
836:(
833:f
813:f
777:.
765:)
762:X
759:(
756:f
753:+
750:)
747:}
742:2
738:x
734:,
729:1
725:x
721:{
715:X
712:(
709:f
703:)
700:}
695:2
691:x
687:{
681:X
678:(
675:f
672:+
669:)
666:}
661:1
657:x
653:{
647:X
644:(
641:f
619:2
615:x
606:1
602:x
581:X
567:2
563:x
559:,
554:1
550:x
523:X
512:.
500:)
497:T
491:S
488:(
485:f
482:+
479:)
476:T
470:S
467:(
464:f
458:)
455:T
452:(
449:f
446:+
443:)
440:S
437:(
434:f
408:T
405:,
402:S
391:.
379:)
376:Y
373:(
370:f
364:)
361:}
358:x
355:{
349:Y
346:(
343:f
337:)
334:X
331:(
328:f
322:)
319:}
316:x
313:{
307:X
304:(
301:f
281:Y
269:x
249:Y
243:X
217:Y
214:,
211:X
157:2
135:R
122:2
118::
115:f
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.