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