3081:
2992:
20:
1317:, with the universe represented by vertices on the left, the sets represented by vertices on the right, and edges representing the membership of elements to sets. The task is then to find a minimum cardinality subset of left-vertices that has a non-trivial intersection with each of the right-vertices, which is precisely the hitting set problem.
471:
is at least 1. The goal is to find a fractional set cover in which the sum of fractions is as small as possible. Note that a (usual) set cover is equivalent to a fractional set cover in which all fractions are either 0 or 1; therefore, the size of the smallest fractional cover is at most the size of
1344:
for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. This method can be implemented in time linear in the sum of sizes of the input sets, using a
3181:
is the problem of selecting a set of vertices (the dominating set) in a graph such that all other vertices are adjacent to at least one vertex in the dominating set. The
Dominating set problem was shown to be NP complete through a reduction from Set
431:
problem, each set is assigned a positive weight (representing its cost), and the goal is to find a set cover with a smallest weight. The usual (unweighted) set cover corresponds to all sets having a weight of 1.
1561:
2491:
745:
234:
2741:
2566:
1070:
2221:
679:
393:
306:
2919:
2069:
1956:
1905:
1732:
1292:
1238:
1127:
862:
777:
1199:
3162:
2289:
830:
2604:
2350:
2154:
Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms (see
1788:
1599:
1260:
461:
258:
196:
172:
148:
2977:
2806:
1839:
1007:
2836:
2322:
1996:
1626:
3936:
3066:
977:
936:
1700:
1669:
2866:
2647:
1726:
2123:
2096:
2023:
1160:
1097:
1454:
1425:
1376:
600:
2149:
3448:
Information., Sandia
National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical (1999).
439:
problem, it is allowed to select fractions of sets, rather than entire sets. A fractional set cover is an assignment of a fraction (a number in ) to each set in
2942:
2764:
2670:
2624:
2423:
1859:
1646:
1474:
1396:
895:
346:
326:
1483:
3857:
1209:
593:
2158:
below), under plausible complexity assumptions. A tighter analysis for the greedy algorithm shows that the approximation ratio is exactly
3203:
is a computational problem equivalent to either listing all minimal hitting sets or listing all minimal set covers of a given set family.
3675:
2432:
586:
3819:
3798:
3758:
3749:(1997), "A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP",
3613:
695:
205:
3475:
3473:
Gainer-Dewar, Andrew; Vera-Licona, Paola (2017), "The minimal hitting set generation problem: algorithms and computation",
2683:
2508:
1018:
3359:
2161:
637:
4026:
3976:
3685:
3339:
404:
358:
271:
2871:
496:
3912:
3877:
44:
3270:
2568:
under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm.
3899:
548:
1015:
is described by a program identical to the one given above, except that the objective function to minimize is
4016:
3022:
2240:
1263:
415:. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of
3164:
and the sets are induced by the intersection of the universe and geometric shapes (e.g., disks, rectangles).
1208:, as all the coefficients in the objective function and both sides of the constraints are non-negative. The
2235:
sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of
4021:
3132:
2028:
1910:
1864:
1269:
1215:
1102:
837:
752:
3092:
3003:
4031:
3329:
1165:
3138:
2249:
790:
4011:
3556:
2575:
2331:
1746:
1568:
1243:
442:
239:
177:
153:
129:
115:, see picture, but not with only one set. Therefore, the solution to the set cover problem for this
3991:
3641:
3172:
2950:
2779:
1793:
983:
416:
3674:
Karpinski, Marek; Zelikovsky, Alexander (1998), "Approximating dense cases of covering problems",
1298:
2815:
2809:
2294:
1961:
1604:
1294:
536:
3829:
3992:
Benchmarks with Hidden
Optimum Solutions for Set Covering, Set Packing and Winner Determination
3921:
3636:
3551:
3036:
1321:
943:
902:
623:
490:
But there is a fractional set cover of size 1.5, in which a 0.5 fraction of each set is taken.
63:
1674:
1651:
2851:
2498:
1743:
There is a standard example on which the greedy algorithm achieves an approximation ratio of
2632:
1705:
3869:
3593:
3506:
3317:
3200:
3120:
2101:
2074:
2001:
1313:. That is seen by observing that an instance of set covering can be viewed as an arbitrary
1138:
1075:
555:
352:
3996:
3677:
Proceedings of the DIMACS Workshop on
Network Design: Connectivity and Facilities Location
1430:
1401:
1352:
8:
3354:
3194:
3185:
3030:
2429:
showed that set covering cannot be approximated in polynomial time to within a factor of
2128:
560:
66:, specifying all possible elements under consideration) and a collection, referred to as
40:
3730:
3703:
3698:
3662:
3627:
3577:
3510:
3484:
3376:
3126:
2927:
2749:
2655:
2609:
2408:
1844:
1631:
1459:
1381:
880:
331:
311:
78:
equals the universe, the set cover problem is to identify a smallest sub-collection of
75:
3290:
1398:
is the size of the set to be covered. In other words, it finds a covering that may be
3972:
3895:
3851:
3815:
3794:
3754:
3751:
STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing
3722:
3681:
3654:
3609:
3569:
3455:
3335:
3295:
898:, where each row corresponds to an element and each column corresponds to a set, and
572:
507:
103:
is equal to 4, as there are four subsets that comprise this collection. The union of
51:
3773:
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing
3666:
3581:
3964:
3957:"Non-approximability results for optimization problems on bounded degree instances"
3941:
3887:
3840:
3734:
3712:
3646:
3597:
3589:
3561:
3514:
3494:
3408:
3368:
3313:
3285:
3068:-factor approximation. Non weighted set cover can be adapted to the weighted case.
1736:
1341:
1205:
874:
567:
512:
265:
36:
3535:
3502:
1477:
1314:
3188:
is to choose a set cover with no element included in more than one covering set.
873:
For a more compact representation of the covering constraint, one can define an
3945:
3807:
3781:
3601:
3325:
3178:
2680:
showed optimal inapproximability by proving that it cannot be approximated to
4005:
3952:
3916:
3785:
3726:
3658:
3573:
3299:
32:
3565:
3459:
3961:
Proceedings of the thirty-third annual ACM symposium on Theory of computing
3908:
3873:
3746:
3694:
3539:
3404:
1346:
543:
472:
the smallest cover, but may be smaller. For example, consider the universe
3968:
3891:
3717:
3650:
3412:
3844:
3837:
Proceedings of the 25th
International Workshop on Principles of Diagnosis
3622:
3372:
3167:
2502:
1324:, a hitting set for a collection of geometrical objects is also called a
524:
408:
400:
3956:
3881:
3080:
2991:
1135:
is described by a program identical to the one given above, except that
3865:
3830:"An Efficient Distributed Algorithm for Computing Minimal Hitting Sets"
3771:; Steurer, David (2013), "Analytical approach to parallel repetition",
3768:
3498:
3380:
3321:
3135:
is a special case of Set Cover when the universe is a set of points in
531:
3531:
3449:
3608:, Cambridge, Mass.: MIT Press and McGraw-Hill, pp. 1033–1038,
3489:
3883:
A new multilayered PCP and the hardness of hypergraph vertex cover
3701:(1994), "On the hardness of approximating minimization problems",
3357:(August 1979), "A Greedy Heuristic for the Set-Covering Problem",
3175:
is to choose at most k sets to cover as many elements as possible.
1565:
This greedy algorithm actually achieves an approximation ratio of
3742:
3680:, vol. 40, American Mathematical Society, pp. 169–178,
1731:
1204:
This linear program belongs to the more general class of LPs for
412:
1556:{\displaystyle H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1}
395:, and the task is to find a set cover that uses the fewest sets.
3542:(2006), "Algorithmic construction of sets for k-restrictions",
2486:{\displaystyle {\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}}
1349:
to prioritize the sets. It achieves an approximation ratio of
3940:, Journal of Computer and System Sciences, pp. 335–349,
2776:
proved it is NP-hard to approximate set cover to better than
2372:
using some polynomial-time method of solving linear programs.
2071:, in that order, while the optimal solution consists only of
3997:
A compendium of NP optimization problems - Minimum Set Cover
3625:(1998), "A threshold of ln n for approximating set cover",
980:
otherwise. Then, the covering constraint can be written as
467:
in the universe, the sum of fractions of sets that contain
19:
3588:
3312:
2848:
proves that set cover instances with sets of size at most
1162:
can be non-integer, so the last constraint is replaced by
3963:, Association for Computing Machinery, pp. 453–461,
3886:, Association for Computing Machinery, pp. 595–601,
3334:(3rd ed.), MIT Press and McGraw-Hill, p. 1122,
3025:
the integer linear program for weighted set cover stated
1262:
is the size of the universe). It has been shown that its
411:
in 1972. The optimization/search version of set cover is
111:. However, we can cover all elements with only two sets:
3214:
3117:
Hitting set is an equivalent reformulation of Set Cover.
2979:
of the greedy algorithm essentially tight in this case.
2626:
is a certain constant, under the weaker assumption that
1998:, each of which contains half of the elements from each
3864:
3472:
3026:
2773:
2353:
328:; the question is whether there is a set cover of size
3918:
Vertex cover might be hard to approximate to within 2−
3405:
A tight analysis of the greedy algorithm for set cover
2437:
1958:
respectively, as well as two additional disjoint sets
1273:
1247:
1219:
740:{\displaystyle \sum _{s\colon e\in s}x_{s}\geqslant 1}
229:{\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}
3924:
3141:
3039:
2953:
2930:
2874:
2854:
2818:
2782:
2752:
2736:{\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}
2686:
2658:
2635:
2612:
2578:
2561:{\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}
2511:
2435:
2411:
2334:
2297:
2252:
2164:
2131:
2104:
2077:
2031:
2025:. On this input, the greedy algorithm takes the sets
2004:
1964:
1913:
1867:
1847:
1796:
1749:
1708:
1677:
1654:
1634:
1607:
1571:
1486:
1462:
1433:
1404:
1384:
1355:
1272:
1246:
1218:
1168:
1141:
1105:
1078:
1065:{\displaystyle \sum _{s\in {\mathcal {S}}}w_{s}x_{s}}
1021:
986:
946:
905:
883:
840:
793:
755:
698:
640:
445:
361:
334:
314:
274:
242:
208:
180:
156:
132:
3673:
3530:
3392:
2673:
3930:
3156:
3060:
2971:
2936:
2913:
2860:
2830:
2800:
2758:
2735:
2664:
2641:
2618:
2598:
2560:
2485:
2417:
2344:
2316:
2283:
2215:
2143:
2117:
2090:
2063:
2017:
1990:
1950:
1899:
1853:
1833:
1782:
1720:
1694:
1663:
1640:
1620:
1593:
1555:
1468:
1448:
1419:
1390:
1370:
1286:
1254:
1232:
1193:
1154:
1121:
1091:
1064:
1001:
971:
930:
889:
856:
824:
771:
739:
673:
455:
387:
340:
320:
300:
252:
228:
190:
166:
142:
3812:Combinatorial Optimization: Theory and Algorithms
2356:, then it becomes a (non-integer) linear program
4003:
2216:{\displaystyle \ln {n}-\ln {\ln {n}}+\Theta (1)}
674:{\displaystyle \sum _{s\in {\mathcal {S}}}x_{s}}
2868:cannot be approximated to a factor better than
388:{\displaystyle ({\mathcal {U}},{\mathcal {S}})}
301:{\displaystyle ({\mathcal {U}},{\mathcal {S}})}
3693:
2914:{\displaystyle \ln \Delta -O(\ln \ln \Delta )}
2426:
2155:
867:(every set is either in the set cover or not)
2714:
2689:
2539:
2514:
2360:. The algorithm can be described as follows:
613:
594:
486:The smallest set cover has a size of 2, e.g.
3827:
3767:
3447:
2677:
2400:
2278:
2266:
819:
807:
23:Example of an instance of set cover problem.
3271:"Fast stabbing of boxes in high dimensions"
3856:: CS1 maint: location missing publisher (
3806:
3220:
2652:. A similar result with a higher value of
1304:
601:
587:
3907:
3716:
3640:
3555:
3488:
3289:
3144:
2839:
1671:dense instances, however, there exists a
1427:times as large as the minimum one, where
3951:
3780:
3741:
3435:
3423:
3256:
3244:
3232:
2845:
2569:
2226:
1730:
399:The decision version of set covering is
97:= { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }.
18:
3353:
3268:
3071:
1297:for the minimum set cover problem. See
4004:
781:(cover every element of the universe)
3621:
2982:
2379:for which the corresponding variable
1841:elements. The set system consists of
3476:SIAM Journal on Discrete Mathematics
3075:
2986:
2505:(1998) improved this lower bound to
2425:refers to the size of the universe,
2352:in the integer linear program shown
85:For example, consider the universe,
3111:
2947:, thus making the approximation of
2674:Alon, Moshkovitz & Safra (2006)
2064:{\displaystyle S_{k},\ldots ,S_{1}}
1951:{\displaystyle 2,4,8,\ldots ,2^{k}}
1900:{\displaystyle S_{1},\ldots ,S_{k}}
1702:-approximation algorithm for every
1335:
1287:{\displaystyle \scriptstyle \log n}
1233:{\displaystyle \scriptstyle \log n}
1122:{\displaystyle s\in {\mathcal {S}}}
857:{\displaystyle s\in {\mathcal {S}}}
772:{\displaystyle e\in {\mathcal {U}}}
622:can be formulated as the following
13:
3828:Cardoso, Nuno; Abreu, Rui (2014),
3454:. United States. Dept. of Energy.
3360:Mathematics of Operations Research
2960:
2905:
2881:
2855:
2337:
2231:If each element occurs in at most
2201:
2125:. An example of such an input for
1628:is the maximum cardinality set of
1613:
1583:
1309:Set covering is equivalent to the
1114:
1035:
849:
764:
654:
448:
377:
367:
290:
280:
245:
221:
211:
183:
159:
135:
82:whose union equals the universe.
16:Classical problem in combinatorics
14:
4043:
3985:
3451:On the Red-Blue Set Cover Problem
3123:is a special case of Hitting Set.
2812:is true, this can be improved to
1194:{\displaystyle 0\leq x_{s}\leq 1}
62:, (henceforth referred to as the
3157:{\displaystyle \mathbb {R} ^{d}}
3079:
2990:
2284:{\displaystyle x_{S}\in \{0,1\}}
825:{\displaystyle x_{s}\in \{0,1\}}
126:More formally, given a universe
3466:
3441:
3429:
3417:
3393:Karpinski & Zelikovsky 1998
3129:is a special case of Set Cover.
3397:
3386:
3347:
3306:
3262:
3250:
3238:
3226:
3055:
3043:
2908:
2890:
2709:
2703:
2599:{\displaystyle c\cdot \ln {n}}
2534:
2528:
2345:{\displaystyle {\mathcal {S}}}
2210:
2204:
1820:
1808:
1783:{\displaystyle \log _{2}(n)/2}
1769:
1763:
1594:{\displaystyle H(s^{\prime })}
1588:
1575:
1496:
1490:
1443:
1437:
1414:
1408:
1365:
1359:
1255:{\displaystyle \scriptstyle n}
939:if element e is in set s, and
685:(minimize the number of sets)
497:Covering/packing-problem pairs
456:{\displaystyle {\mathcal {S}}}
405:Karp's 21 NP-complete problems
382:
362:
295:
275:
253:{\displaystyle {\mathcal {U}}}
191:{\displaystyle {\mathcal {U}}}
167:{\displaystyle {\mathcal {S}}}
143:{\displaystyle {\mathcal {U}}}
1:
3524:
3291:10.1016/S0304-3975(98)00336-3
3269:Nielsen, Frank (2000-09-06).
2972:{\displaystyle \ln \Delta +1}
2801:{\displaystyle f-1-\epsilon }
2572:established a lower bound of
1834:{\displaystyle n=2^{(k+1)}-2}
1002:{\displaystyle Ax\geqslant 1}
484:= { {1, 2}, {2, 3}, {3, 1} }.
463:, such that for each element
3328:(2009) , "Exercise 35.3-3",
3278:Theoretical Computer Science
2427:Lund & Yannakakis (1994)
1301:for a detailed explanation.
1299:randomized rounding#setcover
7:
2831:{\displaystyle f-\epsilon }
2317:{\displaystyle x_{S}\geq 0}
1991:{\displaystyle T_{0},T_{1}}
1790:. The universe consists of
1621:{\displaystyle s^{\prime }}
479:and the collection of sets
422:
92:and the collection of sets
31:is a classical question in
10:
4048:
3946:10.1016/j.jcss.2007.06.019
3606:Introduction to Algorithms
3407:. STOC'96, Pages 435-441,
3331:Introduction to Algorithms
2772:In low-frequency systems,
2678:Dinur & Steurer (2013)
2151:is pictured on the right.
614:Linear program formulation
3931:{\displaystyle \epsilon }
3753:, ACM, pp. 475–484,
3061:{\displaystyle O(\log n)}
2401:Inapproximability results
2364:Find an optimal solution
2156:Inapproximability results
972:{\displaystyle A_{e,s}=0}
931:{\displaystyle A_{e,s}=1}
4027:Approximation algorithms
3814:(5 ed.), Springer,
3787:Approximation Algorithms
3207:
3173:Maximum coverage problem
1861:pairwise disjoint sets
1695:{\displaystyle c\ln {m}}
1664:{\displaystyle \delta -}
417:approximation algorithms
3775:, ACM, pp. 624–633
3566:10.1145/1150334.1150336
2861:{\displaystyle \Delta }
2840:Khot & Regev (2008)
2810:Unique games conjecture
2672:was recently proved by
1305:Hitting set formulation
1295:approximation algorithm
549:Maximum independent set
236:of sets whose union is
3932:
3810:; Vygen, Jens (2012),
3221:Korte & Vygen 2012
3158:
3062:
2973:
2938:
2915:
2862:
2832:
2802:
2760:
2737:
2666:
2643:
2642:{\displaystyle \not =}
2620:
2600:
2570:Raz & Safra (1997)
2562:
2487:
2419:
2346:
2318:
2285:
2217:
2145:
2119:
2092:
2065:
2019:
1992:
1952:
1901:
1855:
1835:
1784:
1740:
1735:Tight example for the
1722:
1721:{\displaystyle c>0}
1696:
1665:
1642:
1622:
1595:
1557:
1522:
1470:
1450:
1421:
1392:
1372:
1322:computational geometry
1288:
1266:indeed gives a factor-
1256:
1234:
1212:of the ILP is at most
1195:
1156:
1123:
1093:
1066:
1003:
973:
932:
891:
858:
826:
773:
741:
675:
624:integer linear program
457:
389:
355:, the input is a pair
342:
322:
302:
268:, the input is a pair
254:
230:
192:
168:
144:
113:{ {1, 2, 3}, {4, 5} }
24:
3969:10.1145/380752.380839
3933:
3892:10.1145/780542.780629
3870:Guruswami, Venkatesan
3718:10.1145/185675.306789
3651:10.1145/285055.285059
3594:Leiserson, Charles E.
3544:ACM Trans. Algorithms
3413:10.1145/237814.237991
3318:Leiserson, Charles E.
3159:
3063:
2974:
2939:
2916:
2863:
2833:
2803:
2761:
2738:
2667:
2644:
2621:
2601:
2563:
2499:quasi-polynomial time
2488:
2420:
2388:has value at least 1/
2347:
2319:
2286:
2227:Low-frequency systems
2218:
2146:
2120:
2118:{\displaystyle T_{1}}
2093:
2091:{\displaystyle T_{0}}
2066:
2020:
2018:{\displaystyle S_{i}}
1993:
1953:
1902:
1856:
1836:
1785:
1734:
1723:
1697:
1666:
1643:
1623:
1596:
1558:
1502:
1471:
1451:
1422:
1393:
1373:
1289:
1257:
1235:
1196:
1157:
1155:{\displaystyle x_{s}}
1124:
1099:is the weight of set
1094:
1092:{\displaystyle w_{s}}
1067:
1004:
974:
933:
892:
859:
827:
774:
742:
676:
458:
390:
343:
323:
303:
255:
231:
193:
169:
145:
22:
4017:NP-complete problems
3922:
3845:10.5281/zenodo.10037
3373:10.1287/moor.4.3.233
3201:Monotone dualization
3139:
3072:Fractional set cover
3037:
2951:
2928:
2872:
2852:
2816:
2780:
2750:
2684:
2656:
2633:
2610:
2576:
2509:
2433:
2409:
2332:
2295:
2250:
2162:
2129:
2102:
2075:
2029:
2002:
1962:
1911:
1865:
1845:
1794:
1747:
1706:
1675:
1652:
1632:
1605:
1569:
1484:
1460:
1449:{\displaystyle H(n)}
1431:
1420:{\displaystyle H(n)}
1402:
1382:
1371:{\displaystyle H(s)}
1353:
1270:
1244:
1216:
1166:
1139:
1133:Fractional set cover
1103:
1076:
1019:
984:
944:
903:
881:
838:
791:
753:
696:
638:
544:Minimum vertex cover
443:
437:fractional set cover
359:
353:optimization problem
332:
312:
272:
240:
206:
178:
154:
130:
3793:, Springer-Verlag,
3699:Yannakakis, Mihalis
3426:, pp. 118–119)
3259:, pp. 110–112)
3195:Set-cover abduction
3191:Red-blue set cover.
3186:Exact cover problem
3133:Geometric set cover
3031:randomized rounding
2774:Dinur et al. (2003)
2144:{\displaystyle k=3}
1311:hitting set problem
525:Maximum set packing
488:{ {1, 2}, {2, 3} }.
41:operations research
4022:Linear programming
3928:
3782:Vazirani, Vijay V.
3704:Journal of the ACM
3628:Journal of the ACM
3499:10.1137/15M1055024
3154:
3091:. You can help by
3058:
3002:. You can help by
2983:Weighted set cover
2969:
2934:
2911:
2858:
2828:
2798:
2756:
2733:
2662:
2639:
2616:
2596:
2558:
2483:
2446:
2415:
2342:
2314:
2281:
2246:If the constraint
2213:
2141:
2115:
2088:
2061:
2015:
1988:
1948:
1897:
1851:
1831:
1780:
1741:
1718:
1692:
1661:
1638:
1618:
1591:
1553:
1466:
1446:
1417:
1388:
1368:
1284:
1283:
1252:
1251:
1230:
1229:
1191:
1152:
1119:
1089:
1062:
1041:
1013:Weighted set cover
999:
969:
928:
887:
854:
822:
769:
737:
720:
671:
660:
532:Minimum edge cover
453:
429:weighted set cover
385:
338:
318:
298:
250:
226:
188:
164:
140:
25:
4032:Covering problems
3839:, Graz, Austria,
3821:978-3-642-24487-2
3800:978-3-540-65367-7
3760:978-0-89791-888-6
3615:978-0-262-03293-3
3598:Rivest, Ronald L.
3590:Cormen, Thomas H.
3322:Rivest, Ronald L.
3314:Cormen, Thomas H.
3109:
3108:
3020:
3019:
2937:{\displaystyle =}
2759:{\displaystyle =}
2665:{\displaystyle c}
2619:{\displaystyle c}
2445:
2418:{\displaystyle n}
1854:{\displaystyle k}
1641:{\displaystyle S}
1531:
1469:{\displaystyle n}
1391:{\displaystyle s}
1206:covering problems
1022:
890:{\displaystyle A}
871:
870:
699:
641:
620:set cover problem
611:
610:
578:
577:
573:Rectangle packing
520:Minimum set cover
508:Covering problems
351:In the set cover
341:{\displaystyle k}
321:{\displaystyle k}
264:In the set cover
99:In this example,
90:= {1, 2, 3, 4, 5}
45:complexity theory
29:set cover problem
4039:
4012:Families of sets
3981:
3948:
3937:
3935:
3934:
3929:
3904:
3861:
3855:
3847:
3834:
3824:
3803:
3792:
3776:
3763:
3737:
3720:
3690:
3669:
3644:
3618:
3584:
3559:
3536:Moshkovitz, Dana
3518:
3517:
3492:
3470:
3464:
3463:
3445:
3439:
3433:
3427:
3421:
3415:
3401:
3395:
3390:
3384:
3383:
3351:
3345:
3344:
3310:
3304:
3303:
3293:
3275:
3266:
3260:
3254:
3248:
3242:
3236:
3230:
3224:
3218:
3163:
3161:
3160:
3155:
3153:
3152:
3147:
3112:Related problems
3104:
3101:
3083:
3076:
3067:
3065:
3064:
3059:
3015:
3012:
2994:
2987:
2978:
2976:
2975:
2970:
2943:
2941:
2940:
2935:
2920:
2918:
2917:
2912:
2867:
2865:
2864:
2859:
2837:
2835:
2834:
2829:
2807:
2805:
2804:
2799:
2765:
2763:
2762:
2757:
2742:
2740:
2739:
2734:
2732:
2718:
2717:
2693:
2692:
2671:
2669:
2668:
2663:
2648:
2646:
2645:
2640:
2625:
2623:
2622:
2617:
2605:
2603:
2602:
2597:
2595:
2567:
2565:
2564:
2559:
2557:
2543:
2542:
2518:
2517:
2492:
2490:
2489:
2484:
2482:
2465:
2457:
2456:
2447:
2438:
2424:
2422:
2421:
2416:
2392:in the solution
2368:for the program
2351:
2349:
2348:
2343:
2341:
2340:
2323:
2321:
2320:
2315:
2307:
2306:
2290:
2288:
2287:
2282:
2262:
2261:
2222:
2220:
2219:
2214:
2197:
2196:
2175:
2150:
2148:
2147:
2142:
2124:
2122:
2121:
2116:
2114:
2113:
2097:
2095:
2094:
2089:
2087:
2086:
2070:
2068:
2067:
2062:
2060:
2059:
2041:
2040:
2024:
2022:
2021:
2016:
2014:
2013:
1997:
1995:
1994:
1989:
1987:
1986:
1974:
1973:
1957:
1955:
1954:
1949:
1947:
1946:
1906:
1904:
1903:
1898:
1896:
1895:
1877:
1876:
1860:
1858:
1857:
1852:
1840:
1838:
1837:
1832:
1824:
1823:
1789:
1787:
1786:
1781:
1776:
1759:
1758:
1737:greedy algorithm
1727:
1725:
1724:
1719:
1701:
1699:
1698:
1693:
1691:
1670:
1668:
1667:
1662:
1647:
1645:
1644:
1639:
1627:
1625:
1624:
1619:
1617:
1616:
1600:
1598:
1597:
1592:
1587:
1586:
1562:
1560:
1559:
1554:
1546:
1532:
1524:
1521:
1516:
1475:
1473:
1472:
1467:
1455:
1453:
1452:
1447:
1426:
1424:
1423:
1418:
1397:
1395:
1394:
1389:
1377:
1375:
1374:
1369:
1342:greedy algorithm
1336:Greedy algorithm
1320:In the field of
1293:
1291:
1290:
1285:
1261:
1259:
1258:
1253:
1239:
1237:
1236:
1231:
1200:
1198:
1197:
1192:
1184:
1183:
1161:
1159:
1158:
1153:
1151:
1150:
1128:
1126:
1125:
1120:
1118:
1117:
1098:
1096:
1095:
1090:
1088:
1087:
1071:
1069:
1068:
1063:
1061:
1060:
1051:
1050:
1040:
1039:
1038:
1008:
1006:
1005:
1000:
978:
976:
975:
970:
962:
961:
937:
935:
934:
929:
921:
920:
896:
894:
893:
888:
875:incidence matrix
863:
861:
860:
855:
853:
852:
831:
829:
828:
823:
803:
802:
778:
776:
775:
770:
768:
767:
746:
744:
743:
738:
730:
729:
719:
680:
678:
677:
672:
670:
669:
659:
658:
657:
629:
628:
603:
596:
589:
568:Polygon covering
537:Maximum matching
513:Packing problems
504:
503:
493:
492:
489:
485:
478:
462:
460:
459:
454:
452:
451:
394:
392:
391:
386:
381:
380:
371:
370:
347:
345:
344:
339:
327:
325:
324:
319:
307:
305:
304:
299:
294:
293:
284:
283:
266:decision problem
259:
257:
256:
251:
249:
248:
235:
233:
232:
227:
225:
224:
215:
214:
197:
195:
194:
189:
187:
186:
173:
171:
170:
165:
163:
162:
149:
147:
146:
141:
139:
138:
122:
118:
114:
110:
106:
102:
98:
91:
81:
73:
69:
61:
37:computer science
4047:
4046:
4042:
4041:
4040:
4038:
4037:
4036:
4002:
4001:
3988:
3979:
3923:
3920:
3919:
3902:
3849:
3848:
3832:
3822:
3808:Korte, Bernhard
3801:
3790:
3761:
3688:
3616:
3602:Stein, Clifford
3557:10.1.1.138.8682
3527:
3522:
3521:
3471:
3467:
3446:
3442:
3434:
3430:
3422:
3418:
3402:
3398:
3391:
3387:
3352:
3348:
3342:
3326:Stein, Clifford
3311:
3307:
3273:
3267:
3263:
3255:
3251:
3243:
3239:
3231:
3227:
3219:
3215:
3210:
3148:
3143:
3142:
3140:
3137:
3136:
3114:
3105:
3099:
3096:
3089:needs expansion
3074:
3038:
3035:
3034:
3016:
3010:
3007:
3000:needs expansion
2985:
2952:
2949:
2948:
2929:
2926:
2925:
2873:
2870:
2869:
2853:
2850:
2849:
2846:Trevisan (2001)
2817:
2814:
2813:
2781:
2778:
2777:
2751:
2748:
2747:
2728:
2713:
2712:
2688:
2687:
2685:
2682:
2681:
2657:
2654:
2653:
2634:
2631:
2630:
2611:
2608:
2607:
2591:
2577:
2574:
2573:
2553:
2538:
2537:
2513:
2512:
2510:
2507:
2506:
2478:
2461:
2452:
2448:
2436:
2434:
2431:
2430:
2410:
2407:
2406:
2403:
2395:
2391:
2387:
2386:
2382:
2378:
2371:
2367:
2359:
2336:
2335:
2333:
2330:
2329:
2327:
2302:
2298:
2296:
2293:
2292:
2291:is replaced by
2257:
2253:
2251:
2248:
2247:
2238:
2234:
2229:
2192:
2185:
2171:
2163:
2160:
2159:
2130:
2127:
2126:
2109:
2105:
2103:
2100:
2099:
2082:
2078:
2076:
2073:
2072:
2055:
2051:
2036:
2032:
2030:
2027:
2026:
2009:
2005:
2003:
2000:
1999:
1982:
1978:
1969:
1965:
1963:
1960:
1959:
1942:
1938:
1912:
1909:
1908:
1891:
1887:
1872:
1868:
1866:
1863:
1862:
1846:
1843:
1842:
1807:
1803:
1795:
1792:
1791:
1772:
1754:
1750:
1748:
1745:
1744:
1707:
1704:
1703:
1687:
1676:
1673:
1672:
1653:
1650:
1649:
1633:
1630:
1629:
1612:
1608:
1606:
1603:
1602:
1582:
1578:
1570:
1567:
1566:
1542:
1523:
1517:
1506:
1485:
1482:
1481:
1478:harmonic number
1461:
1458:
1457:
1432:
1429:
1428:
1403:
1400:
1399:
1383:
1380:
1379:
1354:
1351:
1350:
1338:
1315:bipartite graph
1307:
1271:
1268:
1267:
1245:
1242:
1241:
1217:
1214:
1213:
1210:integrality gap
1179:
1175:
1167:
1164:
1163:
1146:
1142:
1140:
1137:
1136:
1113:
1112:
1104:
1101:
1100:
1083:
1079:
1077:
1074:
1073:
1056:
1052:
1046:
1042:
1034:
1033:
1026:
1020:
1017:
1016:
985:
982:
981:
951:
947:
945:
942:
941:
910:
906:
904:
901:
900:
882:
879:
878:
848:
847:
839:
836:
835:
798:
794:
792:
789:
788:
763:
762:
754:
751:
750:
725:
721:
703:
697:
694:
693:
665:
661:
653:
652:
645:
639:
636:
635:
616:
607:
487:
480:
473:
447:
446:
444:
441:
440:
425:
403:. It is one of
376:
375:
366:
365:
360:
357:
356:
333:
330:
329:
313:
310:
309:
308:and an integer
289:
288:
279:
278:
273:
270:
269:
244:
243:
241:
238:
237:
220:
219:
210:
209:
207:
204:
203:
202:is a subfamily
182:
181:
179:
176:
175:
158:
157:
155:
152:
151:
134:
133:
131:
128:
127:
120:
116:
112:
108:
104:
100:
93:
86:
79:
71:
67:
55:
17:
12:
11:
5:
4045:
4035:
4034:
4029:
4024:
4019:
4014:
4000:
3999:
3994:
3987:
3986:External links
3984:
3983:
3982:
3977:
3953:Trevisan, Luca
3949:
3927:
3905:
3900:
3862:
3825:
3820:
3804:
3799:
3778:
3765:
3759:
3739:
3711:(5): 960–981,
3691:
3686:
3671:
3642:10.1.1.70.5014
3635:(4): 634–652,
3619:
3614:
3586:
3550:(2): 153–177,
3526:
3523:
3520:
3519:
3465:
3440:
3436:Vazirani (2001
3428:
3424:Vazirani (2001
3416:
3396:
3385:
3367:(3): 233–235,
3346:
3340:
3305:
3261:
3257:Vazirani (2001
3249:
3247:, p. 108)
3245:Vazirani (2001
3237:
3233:Vazirani (2001
3225:
3223:, p. 414.
3212:
3211:
3209:
3206:
3205:
3204:
3198:
3192:
3189:
3183:
3179:Dominating set
3176:
3170:
3165:
3151:
3146:
3130:
3124:
3118:
3113:
3110:
3107:
3106:
3100:September 2023
3086:
3084:
3073:
3070:
3057:
3054:
3051:
3048:
3045:
3042:
3029:, one may use
3018:
3017:
2997:
2995:
2984:
2981:
2968:
2965:
2962:
2959:
2956:
2933:
2910:
2907:
2904:
2901:
2898:
2895:
2892:
2889:
2886:
2883:
2880:
2877:
2857:
2827:
2824:
2821:
2797:
2794:
2791:
2788:
2785:
2755:
2731:
2727:
2724:
2721:
2716:
2711:
2708:
2705:
2702:
2699:
2696:
2691:
2661:
2638:
2615:
2594:
2590:
2587:
2584:
2581:
2556:
2552:
2549:
2546:
2541:
2536:
2533:
2530:
2527:
2524:
2521:
2516:
2481:
2477:
2474:
2471:
2468:
2464:
2460:
2455:
2451:
2444:
2441:
2414:
2402:
2399:
2398:
2397:
2393:
2389:
2384:
2383:
2380:
2376:
2375:Pick all sets
2373:
2369:
2365:
2357:
2339:
2325:
2313:
2310:
2305:
2301:
2280:
2277:
2274:
2271:
2268:
2265:
2260:
2256:
2236:
2232:
2228:
2225:
2212:
2209:
2206:
2203:
2200:
2195:
2191:
2188:
2184:
2181:
2178:
2174:
2170:
2167:
2140:
2137:
2134:
2112:
2108:
2085:
2081:
2058:
2054:
2050:
2047:
2044:
2039:
2035:
2012:
2008:
1985:
1981:
1977:
1972:
1968:
1945:
1941:
1937:
1934:
1931:
1928:
1925:
1922:
1919:
1916:
1894:
1890:
1886:
1883:
1880:
1875:
1871:
1850:
1830:
1827:
1822:
1819:
1816:
1813:
1810:
1806:
1802:
1799:
1779:
1775:
1771:
1768:
1765:
1762:
1757:
1753:
1717:
1714:
1711:
1690:
1686:
1683:
1680:
1660:
1657:
1637:
1615:
1611:
1590:
1585:
1581:
1577:
1574:
1552:
1549:
1545:
1541:
1538:
1535:
1530:
1527:
1520:
1515:
1512:
1509:
1505:
1501:
1498:
1495:
1492:
1489:
1465:
1445:
1442:
1439:
1436:
1416:
1413:
1410:
1407:
1387:
1367:
1364:
1361:
1358:
1337:
1334:
1306:
1303:
1282:
1279:
1276:
1250:
1228:
1225:
1222:
1190:
1187:
1182:
1178:
1174:
1171:
1149:
1145:
1116:
1111:
1108:
1086:
1082:
1059:
1055:
1049:
1045:
1037:
1032:
1029:
1025:
998:
995:
992:
989:
968:
965:
960:
957:
954:
950:
927:
924:
919:
916:
913:
909:
886:
869:
868:
865:
851:
846:
843:
832:
821:
818:
815:
812:
809:
806:
801:
797:
786:
783:
782:
779:
766:
761:
758:
747:
736:
733:
728:
724:
718:
715:
712:
709:
706:
702:
691:
687:
686:
683:
681:
668:
664:
656:
651:
648:
644:
633:
615:
612:
609:
608:
606:
605:
598:
591:
583:
580:
579:
576:
575:
570:
564:
563:
558:
552:
551:
546:
540:
539:
534:
528:
527:
522:
516:
515:
510:
500:
499:
450:
424:
421:
397:
396:
384:
379:
374:
369:
364:
349:
337:
317:
297:
292:
287:
282:
277:
247:
223:
218:
213:
185:
174:of subsets of
161:
137:
74:subsets whose
15:
9:
6:
4:
3:
2:
4044:
4033:
4030:
4028:
4025:
4023:
4020:
4018:
4015:
4013:
4010:
4009:
4007:
3998:
3995:
3993:
3990:
3989:
3980:
3978:1-58113-349-9
3974:
3970:
3966:
3962:
3958:
3954:
3950:
3947:
3943:
3939:
3938:
3925:
3914:
3910:
3909:Khot, Subhash
3906:
3903:
3897:
3893:
3889:
3885:
3884:
3879:
3875:
3874:Khot, Subhash
3871:
3867:
3863:
3859:
3853:
3846:
3842:
3838:
3831:
3826:
3823:
3817:
3813:
3809:
3805:
3802:
3796:
3789:
3788:
3783:
3779:
3774:
3770:
3766:
3762:
3756:
3752:
3748:
3747:Safra, Shmuel
3744:
3740:
3736:
3732:
3728:
3724:
3719:
3714:
3710:
3706:
3705:
3700:
3696:
3695:Lund, Carsten
3692:
3689:
3687:9780821870846
3683:
3679:
3678:
3672:
3668:
3664:
3660:
3656:
3652:
3648:
3643:
3638:
3634:
3630:
3629:
3624:
3620:
3617:
3611:
3607:
3603:
3599:
3595:
3591:
3587:
3583:
3579:
3575:
3571:
3567:
3563:
3558:
3553:
3549:
3545:
3541:
3540:Safra, Shmuel
3537:
3533:
3529:
3528:
3516:
3512:
3508:
3504:
3500:
3496:
3491:
3486:
3483:(1): 63–100,
3482:
3478:
3477:
3469:
3461:
3457:
3453:
3452:
3444:
3438:, Chapter 14)
3437:
3432:
3425:
3420:
3414:
3410:
3406:
3403:Slavík Petr
3400:
3394:
3389:
3382:
3378:
3374:
3370:
3366:
3362:
3361:
3356:
3350:
3343:
3341:0-262-03384-4
3337:
3333:
3332:
3327:
3323:
3319:
3315:
3309:
3301:
3297:
3292:
3287:
3283:
3279:
3272:
3265:
3258:
3253:
3246:
3241:
3235:, p. 15)
3234:
3229:
3222:
3217:
3213:
3202:
3199:
3196:
3193:
3190:
3187:
3184:
3180:
3177:
3174:
3171:
3169:
3166:
3149:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3115:
3103:
3094:
3090:
3087:This section
3085:
3082:
3078:
3077:
3069:
3052:
3049:
3046:
3040:
3032:
3028:
3024:
3014:
3011:November 2017
3005:
3001:
2998:This section
2996:
2993:
2989:
2988:
2980:
2966:
2963:
2957:
2954:
2946:
2931:
2924:
2902:
2899:
2896:
2893:
2887:
2884:
2878:
2875:
2847:
2843:
2841:
2838:as proven by
2825:
2822:
2819:
2811:
2795:
2792:
2789:
2786:
2783:
2775:
2770:
2768:
2753:
2746:
2729:
2725:
2722:
2719:
2706:
2700:
2697:
2694:
2679:
2675:
2659:
2651:
2636:
2629:
2613:
2592:
2588:
2585:
2582:
2579:
2571:
2554:
2550:
2547:
2544:
2531:
2525:
2522:
2519:
2504:
2500:
2496:
2479:
2475:
2472:
2469:
2466:
2462:
2458:
2453:
2449:
2442:
2439:
2428:
2412:
2374:
2363:
2362:
2361:
2355:
2311:
2308:
2303:
2299:
2275:
2272:
2269:
2263:
2258:
2254:
2244:
2242:
2241:LP relaxation
2224:
2207:
2198:
2193:
2189:
2186:
2182:
2179:
2176:
2172:
2168:
2165:
2157:
2152:
2138:
2135:
2132:
2110:
2106:
2083:
2079:
2056:
2052:
2048:
2045:
2042:
2037:
2033:
2010:
2006:
1983:
1979:
1975:
1970:
1966:
1943:
1939:
1935:
1932:
1929:
1926:
1923:
1920:
1917:
1914:
1892:
1888:
1884:
1881:
1878:
1873:
1869:
1848:
1828:
1825:
1817:
1814:
1811:
1804:
1800:
1797:
1777:
1773:
1766:
1760:
1755:
1751:
1738:
1733:
1729:
1715:
1712:
1709:
1688:
1684:
1681:
1678:
1658:
1655:
1635:
1609:
1579:
1572:
1563:
1550:
1547:
1543:
1539:
1536:
1533:
1528:
1525:
1518:
1513:
1510:
1507:
1503:
1499:
1493:
1487:
1479:
1463:
1440:
1434:
1411:
1405:
1385:
1362:
1356:
1348:
1343:
1333:
1331:
1327:
1323:
1318:
1316:
1312:
1302:
1300:
1296:
1280:
1277:
1274:
1265:
1248:
1226:
1223:
1220:
1211:
1207:
1202:
1188:
1185:
1180:
1176:
1172:
1169:
1147:
1143:
1134:
1130:
1109:
1106:
1084:
1080:
1057:
1053:
1047:
1043:
1030:
1027:
1023:
1014:
1010:
996:
993:
990:
987:
979:
966:
963:
958:
955:
952:
948:
938:
925:
922:
917:
914:
911:
907:
897:
884:
876:
866:
844:
841:
833:
816:
813:
810:
804:
799:
795:
787:
785:
784:
780:
759:
756:
748:
734:
731:
726:
722:
716:
713:
710:
707:
704:
700:
692:
689:
688:
684:
682:
666:
662:
649:
646:
642:
634:
631:
630:
627:
625:
621:
604:
599:
597:
592:
590:
585:
584:
582:
581:
574:
571:
569:
566:
565:
562:
559:
557:
554:
553:
550:
547:
545:
542:
541:
538:
535:
533:
530:
529:
526:
523:
521:
518:
517:
514:
511:
509:
506:
505:
502:
501:
498:
495:
494:
491:
483:
476:
470:
466:
438:
433:
430:
420:
418:
414:
410:
406:
402:
372:
354:
350:
335:
315:
285:
267:
263:
262:
261:
216:
201:
150:and a family
124:
96:
89:
83:
77:
70:, of a given
65:
59:
53:
48:
46:
42:
38:
34:
33:combinatorics
30:
21:
3960:
3917:
3882:
3836:
3811:
3786:
3772:
3750:
3708:
3702:
3676:
3632:
3626:
3623:Feige, Uriel
3605:
3547:
3543:
3480:
3474:
3468:
3450:
3443:
3431:
3419:
3399:
3388:
3364:
3358:
3349:
3330:
3308:
3284:(1): 53–72.
3281:
3277:
3264:
3252:
3240:
3228:
3216:
3121:Vertex cover
3097:
3093:adding to it
3088:
3021:
3008:
3004:adding to it
2999:
2944:
2922:
2844:
2771:
2766:
2744:
2649:
2627:
2501:algorithms.
2494:
2404:
2245:
2230:
2153:
1742:
1564:
1347:bucket queue
1339:
1330:piercing set
1329:
1326:stabbing set
1325:
1319:
1310:
1308:
1203:
1132:
1131:
1012:
1011:
940:
899:
877:
872:
619:
617:
556:Bin covering
519:
481:
474:
468:
464:
436:
434:
428:
426:
407:shown to be
398:
199:
125:
123:has size 2.
107:is equal to
94:
87:
84:
57:
54:of elements
49:
28:
26:
3913:Regev, Oded
3878:Regev, Oded
3866:Dinur, Irit
3769:Dinur, Irit
3355:Chvatal, V.
3168:Set packing
1907:with sizes
1340:There is a
690:subject to
561:Bin packing
477:= {1, 2, 3}
409:NP-complete
401:NP-complete
4006:Categories
3901:1581136749
3532:Alon, Noga
3525:References
3490:1601.02939
3127:Edge cover
3033:to get an
1264:relaxation
56:{1, 2, …,
3926:ϵ
3727:0004-5411
3659:0004-5411
3637:CiteSeerX
3574:1549-6325
3552:CiteSeerX
3300:0304-3975
3050:
2961:Δ
2958:
2906:Δ
2903:
2897:
2885:−
2882:Δ
2879:
2856:Δ
2826:ϵ
2823:−
2808:. If the
2796:ϵ
2793:−
2787:−
2726:
2720:⋅
2698:−
2589:
2583:⋅
2551:
2545:⋅
2523:−
2493:, unless
2476:
2467:≈
2459:
2309:≥
2264:∈
2202:Θ
2190:
2183:
2177:−
2169:
2046:…
1933:…
1882:…
1826:−
1761:
1685:
1659:−
1656:δ
1614:′
1584:′
1540:
1534:≤
1504:∑
1278:
1224:
1186:≤
1173:≤
1110:∈
1031:∈
1024:∑
994:⩾
845:∈
805:∈
760:∈
732:⩾
714:∈
708::
701:∑
650:∈
643:∑
632:minimize
217:⊆
200:set cover
3955:(2001),
3915:(2008),
3880:(2003),
3852:citation
3784:(2001),
3743:Raz, Ran
3667:52827488
3604:(2001),
3582:11922650
3460:68396743
3023:Relaxing
2637:≠
2606:, where
2324:for all
1739:with k=3
1378:, where
1072:, where
834:for all
749:for all
423:Variants
348:or less.
64:universe
50:Given a
3735:9021065
3515:9240467
3507:3590650
3381:3689577
2921:unless
2743:unless
1456:is the
1240:(where
626:(ILP).
435:In the
427:In the
413:NP-hard
3975:
3898:
3818:
3797:
3757:
3733:
3725:
3684:
3665:
3657:
3639:
3612:
3580:
3572:
3554:
3513:
3505:
3458:
3379:
3338:
3298:
3182:cover.
2239:using
1648:. For
1601:where
43:, and
3833:(PDF)
3791:(PDF)
3731:S2CID
3663:S2CID
3578:S2CID
3511:S2CID
3485:arXiv
3377:JSTOR
3274:(PDF)
3208:Notes
3027:above
2503:Feige
2405:When
2354:above
76:union
3973:ISBN
3896:ISBN
3858:link
3816:ISBN
3795:ISBN
3755:ISBN
3723:ISSN
3682:ISBN
3655:ISSN
3610:ISBN
3570:ISSN
3456:OCLC
3336:ISBN
3296:ISSN
2497:has
2470:0.72
2098:and
1713:>
1476:-th
618:The
198:, a
119:and
47:.
27:The
3965:doi
3942:doi
3888:doi
3841:doi
3713:doi
3647:doi
3562:doi
3495:doi
3409:doi
3369:doi
3286:doi
3282:246
3095:.
3047:log
3006:.
2450:log
2328:in
1752:log
1328:or
1275:log
1221:log
260:.
52:set
4008::
3971:,
3959:,
3911:;
3894:,
3876:;
3872:;
3868:;
3854:}}
3850:{{
3835:,
3745:;
3729:,
3721:,
3709:41
3707:,
3697:;
3661:,
3653:,
3645:,
3633:45
3631:,
3600:;
3596:;
3592:;
3576:,
3568:,
3560:,
3546:,
3538:;
3534:;
3509:,
3503:MR
3501:,
3493:,
3481:31
3479:,
3375:,
3363:,
3324:;
3320:;
3316:;
3294:.
3280:.
3276:.
2955:ln
2945:NP
2900:ln
2894:ln
2876:ln
2842:.
2769:.
2767:NP
2723:ln
2676:.
2650:NP
2586:ln
2548:ln
2495:NP
2473:ln
2243:.
2223:.
2187:ln
2180:ln
2166:ln
1728:.
1682:ln
1537:ln
1480::
1332:.
1201:.
1129:.
1009:.
864:.
419:.
60:}
39:,
35:,
3967::
3944::
3890::
3860:)
3843::
3777:.
3764:.
3738:.
3715::
3670:.
3649::
3585:.
3564::
3548:2
3497::
3487::
3462:.
3411::
3371::
3365:4
3302:.
3288::
3197:.
3150:d
3145:R
3102:)
3098:(
3056:)
3053:n
3044:(
3041:O
3013:)
3009:(
2967:1
2964:+
2932:=
2923:P
2909:)
2891:(
2888:O
2820:f
2790:1
2784:f
2754:=
2745:P
2730:n
2715:)
2710:)
2707:1
2704:(
2701:o
2695:1
2690:(
2660:c
2628:P
2614:c
2593:n
2580:c
2555:n
2540:)
2535:)
2532:1
2529:(
2526:o
2520:1
2515:(
2480:n
2463:n
2454:2
2443:2
2440:1
2413:n
2396:.
2394:O
2390:f
2385:S
2381:x
2377:S
2370:L
2366:O
2358:L
2338:S
2326:S
2312:0
2304:S
2300:x
2279:}
2276:1
2273:,
2270:0
2267:{
2259:S
2255:x
2237:f
2233:f
2211:)
2208:1
2205:(
2199:+
2194:n
2173:n
2139:3
2136:=
2133:k
2111:1
2107:T
2084:0
2080:T
2057:1
2053:S
2049:,
2043:,
2038:k
2034:S
2011:i
2007:S
1984:1
1980:T
1976:,
1971:0
1967:T
1944:k
1940:2
1936:,
1930:,
1927:8
1924:,
1921:4
1918:,
1915:2
1893:k
1889:S
1885:,
1879:,
1874:1
1870:S
1849:k
1829:2
1821:)
1818:1
1815:+
1812:k
1809:(
1805:2
1801:=
1798:n
1778:2
1774:/
1770:)
1767:n
1764:(
1756:2
1716:0
1710:c
1689:m
1679:c
1636:S
1610:s
1589:)
1580:s
1576:(
1573:H
1551:1
1548:+
1544:n
1529:k
1526:1
1519:n
1514:1
1511:=
1508:k
1500:=
1497:)
1494:n
1491:(
1488:H
1464:n
1444:)
1441:n
1438:(
1435:H
1415:)
1412:n
1409:(
1406:H
1386:s
1366:)
1363:s
1360:(
1357:H
1281:n
1249:n
1227:n
1189:1
1181:s
1177:x
1170:0
1148:s
1144:x
1115:S
1107:s
1085:s
1081:w
1058:s
1054:x
1048:s
1044:w
1036:S
1028:s
997:1
991:x
988:A
967:0
964:=
959:s
956:,
953:e
949:A
926:1
923:=
918:s
915:,
912:e
908:A
885:A
850:S
842:s
820:}
817:1
814:,
811:0
808:{
800:s
796:x
765:U
757:e
735:1
727:s
723:x
717:s
711:e
705:s
667:s
663:x
655:S
647:s
602:e
595:t
588:v
482:S
475:U
469:x
465:x
449:S
383:)
378:S
373:,
368:U
363:(
336:k
316:k
296:)
291:S
286:,
281:U
276:(
246:U
222:S
212:C
184:U
160:S
136:U
121:S
117:U
109:U
105:S
101:m
95:S
88:U
80:S
72:m
68:S
58:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
