4692:. Suppose there are three candidates (A, B and C). A single candidate should be elected using the veto voting rule, i.e., each voter vetoes a single candidate and the candidate with the fewest vetoes wins. If a coalition wants to ensure that C is elected, they should partition their vetoes among A and B so as to maximize the smallest number of vetoes each of them gets. If the votes are weighted, then the problem can be reduced to the partition problem, and thus it can be solved efficiently using CKK. For
4144:
4005:
3251:
3676:
3555:
4485:=3, CKK runs substantially faster than CGA on random instances. The advantage of CKK over CGA is much larger in the latter case (when an equal partition exists), and can be of several orders of magnitude. In practice, with
4408:) time. The runtime can be improved by using a greedy heuristic: in each level, develop first the branch in which the current number is put in the set with the smallest sum. This algorithm finds first the solution found by
4277:
2415:
424:
2803:
2278:
2149:
3610:
1195:
228:
in this context is the largest sum in the solution returned by the algorithm, divided by the largest sum in the optimal solution (the ratio is larger than 1). Most algorithms below were developed for
804:
3015:
2944:
2525:
94:
Minimize the difference between the largest sum and the smallest sum. This objective is common in papers about multiway number partitioning, as well as papers originating from physics applications.
169:- a different and harder problem, in which the number of subsets is not considered a fixed parameter, but is determined by the input (the number of sets is the number of integers divided by 3).
926:
3434:
1516:)). Alon, Azar, Woeginger and Yadid presented general PTAS-s (generalizing the PTAS-s of Sanhi, Hochbaum and Shmoys, and Woeginger) for these four problems. Their algorithm works for any
1358:
3097:
4192:
692:
4501:: it finds the KK solution first, and then finds progressively better solutions as time allows (possibly requiring exponential time to reach optimality, for the worst instances). For
1212:
The approximation ratio in this context is the smallest sum in the solution returned by the algorithm, divided by the smallest sum in the optimal solution (the ratio is less than 1).
216:
There are various algorithms that obtain a guaranteed approximation of the optimal solution in polynomial time. There are different approximation algorithms for different objectives.
3714:
483:
2873:
2590:
2063:
1117:
1277:
2706:
978:
4338:, that always find the optimal partition. Since the problem is NP-hard, such algorithms might take exponential time in general, but may be practically usable in certain cases.
854:
3803:
1385:
1308:
1048:
3046:
2636:
2457:
581:
346:
4392:. Each level in the tree corresponds to an input number, where the root corresponds to the largest number, the level below to the next-largest number, etc. Each of the
4039:
3365:
245:
in the scheduling literature) loops over the numbers, and puts each number in the set whose current sum is smallest. If the numbers are not sorted, then the runtime is
1613:. Therefore, the input can be pre-processes by assigning each such input to a unique subset. After this preprocessing, one can assume that all inputs are smaller than
630:
529:
3277:
3845:
3748:
2305:
2176:
306:
272:
3908:
3327:
4467:
4440:
3104:
132:
of parts, each of which has a different lifetime. The goal is to assign the parts to the engines, such that the shortest engine lifetime is as large as possible.
2435:
3618:
124:. It also appears in voting manipulation problems, and in sequencing of maintenance actions for modular gas turbine aircraft engines. Suppose there are some
5309:
3487:
4201:
4154:
Given a desired approximation precision ε>0, let δ>0 be the constant corresponding to ε/3, whose existence is guaranteed by
Condition F*. Let
5694:
2318:
128:
engines, which must be kept working for as long as possible. An engine needs a certain critical part in order to operate. There is a set
355:
109:
represents the time required to complete a single-processor job. The goal is to partition the jobs among the processors such that the
4343:
2722:
2197:
2068:
5325:
28:
of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by
4854:
3562:
1129:
738:
5721:
5570:
5538:
5506:
5387:
5289:
4817:
2949:
2880:
2462:
1198:
716:
4519:
to achieve an even better performance. Their 2018 journal paper summarizes works from several previous conference papers:
543:) sorts the numbers in descending order and repeatedly replaces numbers by their differences. The runtime complexity is
5063:
4884:
862:
735:
and partition them optimally. Then allocate the remaining numbers arbitrarily. This algorithm has approximation ratio
3374:
1821:. The number of these inputs is determined such that the sum of all these new inputs equals the sum of all inputs in
1313:
5276:. Lecture Notes in Computer Science. Vol. 10336. Cham: Springer International Publishing. pp. 127–138.
4850:
3053:
4157:
639:
5677:
5499:
Proceedings of the Twenty-Second
International Joint Conference on Artificial Intelligence - Volume Volume One
4669:
problem, there are constraints on the number of items that can be allocated to each subset (these are called
229:
98:
33:
3684:
429:
5784:
4665:
2829:
2534:
2011:
1060:
4587:
has many fast solvers. A BP solver can be used to find an optimal number partitioning. The idea is to use
1233:
5233:
5192:
4591:
to find the optimal makespan. To initialize the binary search, we need a lower bound and an upper bound:
4474:
2668:
534:
5494:
939:
4409:
4396:
branches corresponds to a different set in which the current number can be put. Traversing the tree in
1392:
1218:
809:
237:
204:
4635:
Some upper bounds can be attained by running heuristic algorithms, such as the greedy algorithm or KK.
3753:
1363:
1285:
1001:
5739:"A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem"
5187:
4840:"Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule"
3020:
2595:
1574:(the number of inputs), but exponential in the approximation precision. The PTAS for minimizing sum(
426:
in general. If the numbers are distributed uniformly in , then the approximation ratio is at most
4639:
Given a lower and an upper bound, run the BP solver with bin size middle := (lower+upper)/2.
4139:{\displaystyle {\frac {d}{d+1}}C_{i}^{\#}-2{\frac {L}{d}}\leq C_{i}\leq C_{i}^{\#}+{\frac {L}{d}}}
3371:
is the original number of inputs. Therefore, the run-time of the dynamic programming algorithm is
2440:
546:
311:
5269:
4588:
90:
sums are "as near as possible". The exact optimization objective can be defined in several ways:
5055:
632:
in general. However, in the average case it performs much better than the greedy algorithm: for
5084:"Using dual approximation algorithms for scheduling problems theoretical and practical results"
3814:
3336:
2654:
1388:
1387:
a huge constant that is exponential in the required approximation factor ε. The algorithm uses
4783:
590:
491:
4959:
4879:
3256:
5380:
Proceedings of the 14th
International Joint Conference on Artificial Intelligence - Volume 1
4000:{\displaystyle C_{i}-{\frac {L}{d}}\leq C_{i}^{\#}\leq {\frac {d+1}{d}}C_{i}+{\frac {L}{d}}}
3820:
3723:
2649:). One way uses dynamic programming: its run-time is a polynomial whose exponent depends on
5675:
5188:"A polynomial-time approximation scheme for maximizing the minimum machine completion time"
4805:
3246:{\displaystyle VAL(k,\mathbf {n} )=\min _{\mathbf {t} \leq \mathbf {n} ,\mathbf {t} \in T}}
2283:
2154:
277:
117:
75:
5587:
248:
8:
5714:
Proceedings of the Twenty-Third
International Joint Conference on Artificial Intelligence
5563:
Proceedings of the Twenty-Third
International Joint Conference on Artificial Intelligence
5531:
Proceedings of the Twenty-Third
International Joint Conference on Artificial Intelligence
4847:
Proceedings of the Twenty-First
International Joint Conference on Artificial Intelligence
4584:
4516:
4490:
4322:) are convex, but they do not satisfy Condition F* above. The proof is by reduction from
3302:
2820:
704:
207:
problem - a more general problem in which different processors may have different speeds.
173:
166:
5636:
5228:
4809:
4449:
4422:
3671:{\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }\cdot \mathbf {t} =\mathbf {n} }
5658:
5617:
5475:
5165:
5113:
5048:
5028:
4981:
4795:
4512:
4397:
3847:), but polynomial in the binary representation of the coefficients, which are in O(log(
2420:
699:
5555:
5523:
5421:
5404:
5205:
4839:
4696:=2, the same is true for any other voting rule that is based on scoring. However, for
5760:
5717:
5688:
5609:
5566:
5534:
5502:
5467:
5426:
5383:
5375:
5329:
5285:
5250:
5246:
5209:
5157:
5105:
5059:
5020:
4940:
4921:"Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System"
4901:
4813:
4761:
4498:
4323:
162:- a special case of multiway number partitioning in which the number of subsets is 2.
159:
5621:
5479:
5169:
5032:
4985:
3858:
5750:
5662:
5648:
5599:
5457:
5416:
5351:
5321:
5277:
5242:
5201:
5147:
5117:
5095:
5012:
5001:"Comparing the minimum completion times of two longest-first scheduling-heuristics"
4971:
4932:
4893:
4753:
4489:=2, problems of arbitrary size can be solved by CKK if the numbers have at most 12
1563:
636:=2, when numbers are distributed uniformly in , its approximation ratio is at most
59:
17:
5709:
5281:
4920:
4741:
4335:
3550:{\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }\cdot f(C(\mathbf {t} ))}
1559:
5592:
Proceedings of the
International Conference on Automated Planning and Scheduling
5382:. IJCAI'95. Montreal, Quebec, Canada: Morgan Kaufmann Publishers Inc.: 266–272.
4654:
bins, then the optimal makespan may be smaller set higher to middle and repeat.
4647:
bins, then the optimal makespan must be larger: set lower to middle and repeat.
1407:
Jin studies a problem in which the goal is to maximize the sum, over every set
5755:
5738:
5604:
5016:
4272:{\displaystyle (1+{\frac {\epsilon }{3}})\cdot OPT\leq (1+\epsilon )\cdot OPT}
1487:
is any fixed function. Similarly, one can minimize the objective function sum(
5778:
5764:
5613:
5471:
5430:
5333:
5254:
5213:
5161:
5109:
5024:
4944:
4919:
Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (1982-06-01).
4905:
4765:
4737:
1620:
There is an optimal partition in which all subsets sums are strictly betweel
1222:, if the numbers are not sorted then the worst-case approximation ratio is 1/
987:
Hochbaum and Shmoys presented the following algorithms, which work even when
485:
121:
29:
5653:
5376:"From approximate to optimal solutions: a case study of number partitioning"
5000:
4976:
2809:
subsets, among all partitions in which all subset sums are strictly between
151:, but there are various algorithms that solve it efficiently in many cases.
116:
Maximize the smallest sum. This objective corresponds to the application of
97:
Minimize the largest sum. This objective is equivalent to one objective for
4511:
presented hybrid algorithms, combining CKK, CGA and other methods from the
3283:-th subset, and combine it with an optimal partition of the remainder into
5152:
5135:
3099:
otherwise - since we do not consider optimal solutions outside this range.
583:. In the worst case, its approximation ratio is similar – at most 7/6 for
5710:"Improved bin completion for optimal bin packing and number partitioning"
5524:"Improved bin completion for optimal bin packing and number partitioning"
5444:
Schreiber, Ethan L.; Korf, Richard E.; Moffitt, Michael D. (2018-07-25).
4800:
4716:
contains code for various number-partitioning and bin-packing algorithms.
184:. The optimization objectives are closely related: the optimal number of
148:
4897:
4880:"Analysis of Greedy Solutions for a Replacement Part Sequencing Problem"
2410:{\displaystyle C(\mathbf {t} )=\sum _{h=d}^{d^{2}}t_{h}\cdot (hL/d^{2})}
1434:
sum of products. This problem has an exact solution that runs in time O(
180:
is flexible; the goal is to find a partition with the smallest possible
4835:
4787:
4389:
3469:
denoting the number of subsets with this configuration. Minimizing sum(
1465:
in a given partition. Instead of minimizing the objective function max(
176:- a dual problem in which the total sum in each subset is bounded, but
5637:"Cached Iterative Weakening for Optimal Multi-Way Number Partitioning"
5326:
10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J
5100:
5083:
5050:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
3017:- since all inputs must be assigned to a single subset, so its sum is
1057:>0, an algorithm with approximation ratio at most (7/6+2 ) in time
998:>0, an algorithm with approximation ratio at most (6/5+2 ) in time
4689:
4282:
1605:, then there is an optimal partition in which one part contains only
5676:
Richard E. Korf, Ethan L. Schreiber, and
Michael D. Moffitt (2014).
5462:
5445:
4936:
4757:
1226:. Sorting the numbers increases the approximation ratio to 5/6 when
5588:"Optimally Scheduling Small Numbers of Identical Parallel Machines"
5308:
Alon, Noga; Azar, Yossi; Woeginger, Gerhard J.; Yadid, Tal (1998).
5270:"Optimal Partitioning Which Maximizes the Weighted Sum of Products"
4713:
3863:
The following lemmas relate the partitions of the rounded instance
1282:
Woeginger presented a PTAS that attains an approximation factor of
1126:>0, an algorithm with approximation ratio at most (1+ε) in time
110:
25:
4700:>2 and other voting rules, some other techniques are required.
694:
in expectation. It also performs better in simulation experiments.
4628:- the size of a bin in the optimal partition of only the largest
3859:
Converting the solution from the rounded to the original instance
2194:). Moreover, each subset can be represented as an integer vector
419:{\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}={\frac {4k-1}{3k}}}
5229:"The exact LPT-bound for maximizing the minimum completion time"
5227:
Csirik, János; Kellerer, Hans; Woeginger, Gerhard (1992-06-01).
4688:
One application of the partition problem is for manipulation of
2065:. Therefore, the input can be represented as an integer vector
5501:. IJCAI'11. Barcelona, Catalonia, Spain: AAAI Press: 591–596.
4473:-tuples. This algorithm finds first the solution found by the
4369:
is the largest number in the input. It is practical only when
2798:{\displaystyle \mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})}
2273:{\displaystyle \mathbf {t} =(t_{d},t_{d+1},\ldots ,t_{d^{2}})}
2144:{\displaystyle \mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})}
1651:). Particularly, the partition minimizing the sum of squares
5641:
Proceedings of the AAAI Conference on Artificial Intelligence
5556:"Search strategies for optimal multi-way number partitioning"
5360:
4315:
2708:
as the optimal (minimum) value of the objective function sum(
1658:, among all optimal partitions, satisfies these inequalities.
5495:"A hybrid recursive multi-way number partitioning algorithm"
2641:
There are two different ways to find an optimal solution to
5310:"Approximation schemes for scheduling on parallel machines"
4469:
branches corresponds to a different way of combining these
3817:
can be used. Its run-time is exponential in the dimension (
3605:{\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }=k}
36:
problem. The problem is parametrized by a positive integer
4419:
considers all partitions by constructing a tree of degree
1190:{\displaystyle O((n/\varepsilon )^{(1/\varepsilon ^{2})})}
723:
Graham presented the following algorithm. For any integer
4918:
4497:=3, at most 6 significant digits. CKK can also run as an
2527:. Since the sum of elements in such a vector is at most 2
1441:
799:{\displaystyle 1+{\frac {1-1/k}{1+\lfloor r/k\rfloor }}}
5226:
4960:"Objective Functions for Multi-Way Number Partitioning"
3010:{\displaystyle L^{\#}/2<C(\mathbf {n} ))<2L^{\#}}
5647:. Québec City, Québec, Canada: AAAI Press: 2738–2744.
5405:"A complete anytime algorithm for number partitioning"
5307:
4505:≥ 4, CKK becomes much slower, and CGA performs better.
3447:
2939:{\displaystyle VAL(1,\mathbf {n} )=f(C(\mathbf {n} ))}
2520:{\displaystyle L^{\#}/2<C(\mathbf {t} )<2L^{\#}}
1528:: for every ε>0 there exists δ>0 such that, if |
4452:
4425:
4204:
4194:. It is possible to show that converted partition of
4160:
4042:
3911:
3823:
3756:
3726:
3687:
3621:
3565:
3490:
3480:)) can be attained by the solving the following ILP:
3377:
3339:
3305:
3259:
3107:
3056:
3023:
2952:
2883:
2832:
2725:
2671:
2598:
2537:
2531:, the total number of these elements is smaller than
2465:
2443:
2423:
2321:
2286:
2200:
2157:
2071:
2014:
1366:
1316:
1288:
1236:
1132:
1063:
1004:
942:
865:
859:
Sahni presented a PTAS that attains (1+ε)OPT in time
812:
741:
707:. In the worst case, its makespan is at most 8/7 for
642:
593:
549:
494:
432:
358:
314:
280:
251:
5708:
Schreiber, Ethan L.; Korf, Richard E. (2013-08-03).
5635:
Schreiber, Ethan L.; Korf, Richard E. (2014-07-27).
5522:
Schreiber, Ethan L.; Korf, Richard E. (2013-08-03).
5443:
3299:, the recurrence relation requires to check at most
136:
These three objective functions are equivalent when
70:
subsets such that the sum of each subset is exactly
5082:Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01).
5716:. IJCAI '13. Beijing, China: AAAI Press: 651–658.
5678:"Optimal Sequential Multi-Way Number Partitioning"
5565:. IJCAI '13. Beijing, China: AAAI Press: 623–629.
5533:. IJCAI '13. Beijing, China: AAAI Press: 651–658.
5047:
4477:, but then proceeds to find better solutions. For
4461:
4434:
4283:Non-existence of PTAS for some objective functions
4271:
4186:
4138:
3999:
3839:
3797:
3742:
3708:
3670:
3604:
3549:
3428:
3359:
3321:
3271:
3245:
3091:
3040:
3009:
2938:
2867:
2797:
2700:
2630:
2584:
2519:
2451:
2429:
2409:
2299:
2272:
2170:
2143:
2057:
1837:(for example, if the sum of all "short" inputs in
1379:
1352:
1302:
1271:
1189:
1111:
1042:
972:
920:
848:
798:
703:uses binary search combined with an algorithm for
686:
624:
575:
523:
477:
418:
340:
300:
266:
4877:
4412:, but then proceeds to look for better solutions.
1402:
921:{\displaystyle O(n\cdot (n^{2}/\epsilon )^{k-1})}
348:and improves the approximation ratio to 7/6 when
5776:
4878:Friesen, D. K.; Deuermeyer, B. L. (1981-02-01).
4792:Computational complexity and statistical physics
3138:
1956:) in which all subset sums are strictly between
1877:. Moreover, the above two observations hold for
1585:)) is based on some combinatorial observations:
1398:The FPTAS of Sahni works for this objective too.
192:, iff the optimal size of a largest subset in a
5005:Central European Journal of Operations Research
4830:
4828:
4784:"The Easiest Hard Problem: Number Partitioning"
3429:{\displaystyle O(k\cdot n^{d^{2}}\cdot d^{4d})}
2660:
1593: := the average sum in a single subset (1/
1472:), one can minimize the objective function max(
308:. Sorting the numbers increases the runtime to
113:(the finish time of the last job) is minimized.
5586:Korf, Richard; Schreiber, Ethan (2013-06-02).
5081:
4964:Third Annual Symposium on Combinatorial Search
4925:SIAM Journal on Algebraic and Discrete Methods
4291:In contrast to the above result, if we take f(
1520:which satisfies the following two conditions:
1207:
5737:Pop, Petrică C.; Matei, Oliviu (2013-11-01).
5707:
5634:
5585:
5521:
5272:. In Xiao, Mingyu; Rosamond, Frances (eds.).
5136:"Algorithms for Scheduling Independent Tasks"
5046:Garey, Michael R.; Johnson, David S. (1979).
3851:)). Constructing the ILP itself takes time O(
2315:inputs in the subset. The subset sum is then
1833:, rounded up to the next integer multiple of
219:
5693:: CS1 maint: multiple names: authors list (
5045:
4825:
4742:"Bounds on Multiprocessing Timing Anomalies"
4595:Some lower bounds on the makespan are: (sum
4545:Hybrid recursive number partitioning (HRNP).
4181:
4167:
1353:{\displaystyle O(c_{\varepsilon }n\log {k})}
790:
776:
51:of numbers (usually integers), whose sum is
4794:, Oxford University Press US, p. 125,
4578:
4384:considers all partitions by constructing a
3092:{\displaystyle VAL(1,\mathbf {n} )=\infty }
1988:Based on these observations, all inputs in
1733:rounded up to the next integer multiple of
211:
4187:{\displaystyle d:=\lceil 5/\delta \rceil }
5754:
5652:
5603:
5461:
5420:
5185:
5151:
5099:
4975:
4845:. Written at Pasadena, California, USA.
4799:
4344:pseudopolynomial time number partitioning
1925:, the rounding-up of inputs smaller than
1893:be the average sum in a single subset (1/
1570:The runtime of their PTAS-s is linear in
687:{\displaystyle 1+1/n^{\Theta (\log {n})}}
105:identical processors, and each number in
47:. The input to the problem is a multiset
5736:
5345:
5343:
1964:Therefore, all subsets contain at most 2
980:. The algorithm uses a technique called
5553:
5446:"Optimal Multi-Way Number Partitioning"
4781:
4417:Complete Karmarkar-Karp algorithm (CKK)
1869:), all inputs are integer multiples of
274:and the approximation ratio is at most
5777:
5129:
5127:
4998:
4736:
4442:. Each level corresponds to a pair of
3709:{\displaystyle x_{\mathbf {t} }\geq 0}
1597:the sum of all inputs). If some input
1442:A PTAS for general objective functions
1419:. In a more general variant, each set
478:{\displaystyle 1+O(\log {\log {n}}/n)}
5340:
5303:
5301:
5181:
5179:
5133:
5077:
5075:
5054:. W. H. Freeman and Company. p.
4834:
4732:
4730:
4377:=3 and the inputs are small integers.
4303:-1), then no PTAS for minimizing sum(
4279:, so the approximation ratio is 1+ε.
3329:vectors. The total number of vectors
2875:- since their objective sum is empty.
2868:{\displaystyle VAL(0,\mathbf {0} )=0}
2585:{\displaystyle {(d^{2})}^{2d}=d^{4d}}
2058:{\displaystyle (d,d+1,\ldots ,d^{2})}
1609:. This follows from the convexity of
1524:A strong continuity condition called
1112:{\displaystyle O(n(rk^{4}+\log {n}))}
717:polynomial-time approximation schemes
5492:
5402:
5373:
5349:
5186:Woeginger, Gerhard J. (1997-05-01).
4957:
4786:, in Allon Percus; Gabriel Istrate;
4777:
4775:
4678:multidimensional number partitioning
3805:- both are constants independent of
1666:technique. Given the input sequence
1272:{\displaystyle {\frac {3k-1}{4k-2}}}
140:=2, but they are all different when
5267:
5124:
4746:SIAM Journal on Applied Mathematics
4523:Recursive Number Partitioning (RNP)
4329:
3720:The number of variables is at most
3448:Integer linear programming solution
2701:{\displaystyle VAL(k,\mathbf {n} )}
1562:(for the minimization problems) or
1415:, of the product of numbers in set
154:Some closely-related problems are:
13:
5554:Moffitt, Michael D. (2013-08-03).
5367:
5298:
5176:
5072:
4885:Mathematics of Operations Research
4849:. San Francisco, California, USA:
4727:
4703:
4118:
4071:
3948:
3086:
3002:
2958:
2819:It can be solved by the following
2805:and it has to be partitioned into
2512:
2471:
1430:, and the goal is to maximize the
973:{\displaystyle O(n^{2}/\epsilon )}
662:
14:
5796:
4958:Korf, Richard Earl (2010-08-25).
4772:
4643:If the result contains more than
4565:Cached iterative weakening (CIW).
3750:, and the number of equations is
1948:There is an optimal partition of
1917:itself is an integer multiple of
849:{\displaystyle O(2^{r}n\log {n})}
711:=2, and at most 13/11 in general.
24:is the problem of partitioning a
4603:- the average value per subset,
4146:, and it can be found in time O(
3798:{\displaystyle d^{4d}+d^{2}-d+2}
3694:
3664:
3656:
3646:
3628:
3590:
3572:
3537:
3515:
3497:
3233:
3225:
3187:
3159:
3151:
3143:
3127:
3076:
3031:
2981:
2926:
2903:
2852:
2727:
2691:
2657:for integer linear programming.
2494:
2445:
2329:
2202:
2073:
1817:) contains some inputs equal to
1566:(for the maximization problems).
1380:{\displaystyle c_{\varepsilon }}
1303:{\displaystyle 1-{\varepsilon }}
1043:{\displaystyle O(n(r+\log {n}))}
5730:
5701:
5669:
5628:
5579:
5547:
5515:
5493:Korf, Richard E. (2011-07-16).
5486:
5437:
5403:Korf, Richard E. (1998-12-01).
5396:
5374:Korf, Richard E. (1995-08-20).
5261:
5220:
5134:Sahni, Sartaj K. (1976-01-01).
4860:from the original on 2020-07-10
4851:Morgan Kaufmann Publishers Inc.
4683:
4650:If the result contains at most
4382:Complete Greedy Algorithm (CGA)
3279:: we check all options for the
3041:{\displaystyle C(\mathbf {n} )}
5743:Applied Mathematical Modelling
5039:
4992:
4951:
4912:
4871:
4254:
4242:
4224:
4205:
3544:
3541:
3533:
3527:
3423:
3381:
3315:
3307:
3240:
3237:
3209:
3194:
3191:
3183:
3177:
3171:
3131:
3117:
3080:
3066:
3035:
3027:
2988:
2985:
2977:
2933:
2930:
2922:
2916:
2907:
2893:
2856:
2842:
2792:
2734:
2695:
2681:
2631:{\displaystyle |T|\leq d^{4d}}
2608:
2600:
2553:
2540:
2498:
2490:
2404:
2380:
2333:
2325:
2267:
2209:
2138:
2080:
2052:
2015:
1968:elements (since all inputs in
1403:Maximizing the sum of products
1347:
1320:
1184:
1179:
1158:
1154:
1139:
1136:
1106:
1103:
1073:
1067:
1037:
1034:
1014:
1008:
967:
946:
915:
900:
878:
869:
843:
816:
679:
665:
570:
553:
518:
504:
472:
442:
335:
318:
261:
255:
32:in 1969 in the context of the
1:
5422:10.1016/S0004-3702(98)00086-1
5353:Multi-Way Number Partitioning
5206:10.1016/S0167-6377(96)00055-7
4720:
3612:(the total number of subsets)
2719:)), when the input vector is
1929:cannot make them larger than
936:=2, the run-time improves to
230:identical-machines scheduling
99:Identical-machines scheduling
34:identical-machines scheduling
5282:10.1007/978-3-319-59605-1_12
5247:10.1016/0167-6377(92)90004-M
4666:balanced number partitioning
4533:>2 it recursively splits
4198:has a total cost of at most
3871:) and the original instance
3678:(the total vector of inputs)
2661:Dynamic programming solution
2452:{\displaystyle \mathbf {t} }
1279:in general, and it is tight.
719:(PTAS) have been developed:
576:{\displaystyle O(n\log {n})}
341:{\displaystyle O(n\log {n})}
22:multiway number partitioning
7:
5234:Operations Research Letters
5193:Operations Research Letters
4999:Walter, Rico (2013-01-01).
4658:
4555:Improved search strategies.
4509:Korf, Schreiber and Moffitt
4475:largest differencing method
2008:is an integer in the range
1945:, and hence smaller than L.
1933:. Therefore, all inputs in
1208:Maximizing the smallest sum
536:Largest Differencing Method
205:uniform-machines scheduling
10:
5801:
4410:greedy number partitioning
4404:) space, but might take O(
4025:, there is a partition of
3890:, there is a partition of
1809:In addition, the sequence
1393:integer linear programming
1219:greedy number partitioning
238:Greedy number partitioning
220:Minimizing the largest sum
5756:10.1016/j.apm.2013.03.075
5605:10.1609/icaps.v23i1.13544
5350:Korf, Richard E. (2009).
5274:Frontiers in Algorithmics
5017:10.1007/s10100-011-0217-4
4782:Mertens, Stephan (2006),
4446:-tuples, and each of the
3360:{\displaystyle n^{d^{2}}}
1897:the sum of all inputs in
1696:) is defined as follows:
1684:) and a positive integer
4610:- the largest number in
4579:Reduction to bin packing
4550:Improved bin completion.
4537:into subsets and splits
4010:For every partition of
625:{\displaystyle 4/3-1/3k}
541:Karmarkar-Karp algorithm
524:{\displaystyle 1+O(1/n)}
212:Approximation algorithms
66:can be partitioned into
45:-way number partitioning
5654:10.1609/aaai.v28i1.9122
5409:Artificial Intelligence
4977:10.1609/socs.v1i1.18172
4676:Another variant is the
4671:cardinality constraints
4570:Sequential partitioning
4560:Few machines algorithm.
3879:For every partition of
3460:, introduce a variable
3272:{\displaystyle k\geq 2}
1688:, the rounded sequence
1461:) be the sum of subset
243:Largest Processing Time
188:-sized bins is at most
147:All these problems are
86:subsets, such that the
4463:
4436:
4400:order requires only O(
4273:
4188:
4140:
4001:
3841:
3840:{\displaystyle d^{4d}}
3799:
3744:
3743:{\displaystyle d^{4d}}
3710:
3672:
3606:
3551:
3430:
3361:
3323:
3273:
3247:
3093:
3042:
3011:
2940:
2869:
2799:
2702:
2632:
2586:
2521:
2453:
2431:
2411:
2366:
2301:
2274:
2172:
2145:
2059:
1498:)), or maximize min(f(
1381:
1354:
1304:
1273:
1191:
1113:
1044:
991:is part of the input.
974:
922:
850:
800:
688:
626:
577:
525:
479:
420:
342:
302:
268:
196:-partition is at most
78:: find a partition of
5314:Journal of Scheduling
5153:10.1145/321921.321934
4464:
4437:
4274:
4189:
4141:
4002:
3842:
3800:
3745:
3711:
3673:
3607:
3552:
3431:
3362:
3324:
3274:
3248:
3094:
3043:
3012:
2941:
2870:
2800:
2703:
2653:. The other way uses
2633:
2587:
2522:
2454:
2437:, the set of vectors
2432:
2412:
2339:
2302:
2300:{\displaystyle x_{h}}
2275:
2173:
2171:{\displaystyle n_{h}}
2146:
2060:
1905:)). By construction,
1382:
1355:
1305:
1274:
1192:
1114:
1045:
982:interval partitioning
975:
923:
851:
801:
689:
627:
578:
526:
480:
421:
343:
303:
301:{\displaystyle 2-1/k}
269:
62:is to decide whether
4450:
4423:
4318:. Note that these f(
4202:
4158:
4040:
3909:
3821:
3754:
3724:
3685:
3619:
3563:
3488:
3375:
3337:
3333:to check is at most
3303:
3257:
3105:
3054:
3021:
2950:
2881:
2830:
2723:
2669:
2596:
2535:
2463:
2441:
2421:
2319:
2284:
2198:
2155:
2069:
2012:
1849:inputs are added to
1719:) contains an input
1505:)), or maximize sum(
1364:
1314:
1286:
1234:
1130:
1061:
1002:
940:
928:. It is an FPTAS if
863:
810:
806:and it runs in time
739:
640:
591:
547:
492:
430:
356:
312:
278:
267:{\displaystyle O(n)}
249:
118:fair item allocation
76:optimization problem
5785:Number partitioning
4898:10.1287/moor.6.1.74
4810:2003cond.mat.10317M
4585:bin packing problem
4517:bin packing problem
4122:
4075:
3952:
3815:Lenstra's algorithm
3322:{\displaystyle |T|}
2821:recurrence relation
2655:Lenstra's algorithm
1941:) are smaller than
1829:) that are at most
1389:Lenstra's algorithm
731:largest numbers in
226:approximation ratio
174:bin packing problem
167:3-partition problem
120:, particularly the
74:. There is also an
5450:Journal of the ACM
5140:Journal of the ACM
5088:Journal of the ACM
4853:pp. 324–329.
4513:subset sum problem
4462:{\displaystyle k!}
4459:
4435:{\displaystyle k!}
4432:
4269:
4184:
4136:
4108:
4061:
3997:
3938:
3837:
3795:
3740:
3706:
3668:
3639:
3602:
3583:
3547:
3508:
3436:. It is linear in
3426:
3357:
3319:
3269:
3243:
3170:
3089:
3038:
3007:
2936:
2865:
2795:
2698:
2628:
2582:
2517:
2449:
2427:
2407:
2297:
2270:
2168:
2141:
2055:
1996:) are of the form
1423:may have a weight
1377:
1350:
1300:
1269:
1187:
1109:
1040:
970:
918:
846:
796:
700:Multifit algorithm
684:
622:
573:
521:
475:
416:
338:
298:
264:
5749:(22): 9191–9202.
5723:978-1-57735-633-2
5572:978-1-57735-633-2
5540:978-1-57735-633-2
5508:978-1-57735-513-7
5456:(4): 24:1–24:61.
5389:978-1-55860-363-9
5291:978-3-319-59605-1
5268:Jin, Kai (2017).
5101:10.1145/7531.7535
4819:978-0-19-517737-4
4499:anytime algorithm
4491:significant digit
4324:partition problem
4314:)) exists unless
4222:
4134:
4090:
4059:
3995:
3972:
3933:
3622:
3566:
3491:
3137:
2430:{\displaystyle T}
2307:is the number of
2178:is the number of
1662:The PTAS uses an
1267:
794:
539:(also called the
414:
385:
367:
241:(also called the
160:partition problem
5792:
5769:
5768:
5758:
5734:
5728:
5727:
5705:
5699:
5698:
5692:
5684:
5682:
5673:
5667:
5666:
5656:
5632:
5626:
5625:
5607:
5583:
5577:
5576:
5560:
5551:
5545:
5544:
5528:
5519:
5513:
5512:
5490:
5484:
5483:
5465:
5441:
5435:
5434:
5424:
5400:
5394:
5393:
5371:
5365:
5364:
5358:
5347:
5338:
5337:
5305:
5296:
5295:
5265:
5259:
5258:
5224:
5218:
5217:
5183:
5174:
5173:
5155:
5131:
5122:
5121:
5103:
5079:
5070:
5069:
5053:
5043:
5037:
5036:
4996:
4990:
4989:
4979:
4955:
4949:
4948:
4916:
4910:
4909:
4875:
4869:
4868:
4866:
4865:
4859:
4844:
4832:
4823:
4822:
4803:
4801:cond-mat/0310317
4788:Cristopher Moore
4779:
4770:
4769:
4734:
4468:
4466:
4465:
4460:
4441:
4439:
4438:
4433:
4368:
4364:
4336:exact algorithms
4330:Exact algorithms
4278:
4276:
4275:
4270:
4223:
4215:
4193:
4191:
4190:
4185:
4177:
4145:
4143:
4142:
4137:
4135:
4127:
4121:
4116:
4104:
4103:
4091:
4083:
4074:
4069:
4060:
4058:
4044:
4006:
4004:
4003:
3998:
3996:
3988:
3983:
3982:
3973:
3968:
3957:
3951:
3946:
3934:
3926:
3921:
3920:
3846:
3844:
3843:
3838:
3836:
3835:
3804:
3802:
3801:
3796:
3782:
3781:
3769:
3768:
3749:
3747:
3746:
3741:
3739:
3738:
3715:
3713:
3712:
3707:
3699:
3698:
3697:
3677:
3675:
3674:
3669:
3667:
3659:
3651:
3650:
3649:
3638:
3631:
3611:
3609:
3608:
3603:
3595:
3594:
3593:
3582:
3575:
3556:
3554:
3553:
3548:
3540:
3520:
3519:
3518:
3507:
3500:
3452:For each vector
3435:
3433:
3432:
3427:
3422:
3421:
3406:
3405:
3404:
3403:
3366:
3364:
3363:
3358:
3356:
3355:
3354:
3353:
3328:
3326:
3325:
3320:
3318:
3310:
3278:
3276:
3275:
3270:
3252:
3250:
3249:
3244:
3236:
3228:
3190:
3169:
3162:
3154:
3146:
3130:
3098:
3096:
3095:
3090:
3079:
3047:
3045:
3044:
3039:
3034:
3016:
3014:
3013:
3008:
3006:
3005:
2984:
2967:
2962:
2961:
2945:
2943:
2942:
2937:
2929:
2906:
2874:
2872:
2871:
2866:
2855:
2804:
2802:
2801:
2796:
2791:
2790:
2789:
2788:
2765:
2764:
2746:
2745:
2730:
2707:
2705:
2704:
2699:
2694:
2637:
2635:
2634:
2629:
2627:
2626:
2611:
2603:
2591:
2589:
2588:
2583:
2581:
2580:
2565:
2564:
2556:
2552:
2551:
2526:
2524:
2523:
2518:
2516:
2515:
2497:
2480:
2475:
2474:
2458:
2456:
2455:
2450:
2448:
2436:
2434:
2433:
2428:
2416:
2414:
2413:
2408:
2403:
2402:
2393:
2376:
2375:
2365:
2364:
2363:
2353:
2332:
2306:
2304:
2303:
2298:
2296:
2295:
2279:
2277:
2276:
2271:
2266:
2265:
2264:
2263:
2240:
2239:
2221:
2220:
2205:
2177:
2175:
2174:
2169:
2167:
2166:
2150:
2148:
2147:
2142:
2137:
2136:
2135:
2134:
2111:
2110:
2092:
2091:
2076:
2064:
2062:
2061:
2056:
2051:
2050:
1386:
1384:
1383:
1378:
1376:
1375:
1359:
1357:
1356:
1351:
1346:
1332:
1331:
1309:
1307:
1306:
1301:
1299:
1278:
1276:
1275:
1270:
1268:
1266:
1252:
1238:
1196:
1194:
1193:
1188:
1183:
1182:
1178:
1177:
1168:
1149:
1118:
1116:
1115:
1110:
1102:
1088:
1087:
1049:
1047:
1046:
1041:
1033:
979:
977:
976:
971:
963:
958:
957:
927:
925:
924:
919:
914:
913:
895:
890:
889:
855:
853:
852:
847:
842:
828:
827:
805:
803:
802:
797:
795:
793:
786:
768:
764:
749:
693:
691:
690:
685:
683:
682:
678:
656:
631:
629:
628:
623:
615:
601:
587:=2, and at most
582:
580:
579:
574:
569:
530:
528:
527:
522:
514:
484:
482:
481:
476:
468:
463:
462:
425:
423:
422:
417:
415:
413:
405:
391:
386:
384:
373:
368:
360:
347:
345:
344:
339:
334:
307:
305:
304:
299:
294:
273:
271:
270:
265:
60:decision problem
18:computer science
5800:
5799:
5795:
5794:
5793:
5791:
5790:
5789:
5775:
5774:
5773:
5772:
5735:
5731:
5724:
5706:
5702:
5686:
5685:
5680:
5674:
5670:
5633:
5629:
5584:
5580:
5573:
5558:
5552:
5548:
5541:
5526:
5520:
5516:
5509:
5491:
5487:
5463:10.1145/3184400
5442:
5438:
5401:
5397:
5390:
5372:
5368:
5356:
5348:
5341:
5306:
5299:
5292:
5266:
5262:
5225:
5221:
5184:
5177:
5132:
5125:
5080:
5073:
5066:
5044:
5040:
4997:
4993:
4956:
4952:
4937:10.1137/0603019
4917:
4913:
4876:
4872:
4863:
4861:
4857:
4842:
4833:
4826:
4820:
4780:
4773:
4758:10.1137/0117039
4735:
4728:
4723:
4706:
4704:Implementations
4686:
4661:
4627:
4620:
4609:
4581:
4451:
4448:
4447:
4424:
4421:
4420:
4366:
4347:
4332:
4312:
4285:
4214:
4203:
4200:
4199:
4173:
4159:
4156:
4155:
4126:
4117:
4112:
4099:
4095:
4082:
4070:
4065:
4048:
4043:
4041:
4038:
4037:
4034:
4023:
3987:
3978:
3974:
3958:
3956:
3947:
3942:
3925:
3916:
3912:
3910:
3907:
3906:
3903:
3888:
3861:
3828:
3824:
3822:
3819:
3818:
3777:
3773:
3761:
3757:
3755:
3752:
3751:
3731:
3727:
3725:
3722:
3721:
3693:
3692:
3688:
3686:
3683:
3682:
3663:
3655:
3645:
3644:
3640:
3627:
3626:
3620:
3617:
3616:
3589:
3588:
3584:
3571:
3570:
3564:
3561:
3560:
3536:
3514:
3513:
3509:
3496:
3495:
3489:
3486:
3485:
3478:
3468:
3450:
3414:
3410:
3399:
3395:
3394:
3390:
3376:
3373:
3372:
3349:
3345:
3344:
3340:
3338:
3335:
3334:
3314:
3306:
3304:
3301:
3300:
3258:
3255:
3254:
3232:
3224:
3186:
3158:
3150:
3142:
3141:
3126:
3106:
3103:
3102:
3075:
3055:
3052:
3051:
3030:
3022:
3019:
3018:
3001:
2997:
2980:
2963:
2957:
2953:
2951:
2948:
2947:
2925:
2902:
2882:
2879:
2878:
2851:
2831:
2828:
2827:
2784:
2780:
2779:
2775:
2754:
2750:
2741:
2737:
2726:
2724:
2721:
2720:
2717:
2690:
2670:
2667:
2666:
2663:
2619:
2615:
2607:
2599:
2597:
2594:
2593:
2573:
2569:
2557:
2547:
2543:
2539:
2538:
2536:
2533:
2532:
2511:
2507:
2493:
2476:
2470:
2466:
2464:
2461:
2460:
2444:
2442:
2439:
2438:
2422:
2419:
2418:
2398:
2394:
2389:
2371:
2367:
2359:
2355:
2354:
2343:
2328:
2320:
2317:
2316:
2291:
2287:
2285:
2282:
2281:
2259:
2255:
2254:
2250:
2229:
2225:
2216:
2212:
2201:
2199:
2196:
2195:
2162:
2158:
2156:
2153:
2152:
2130:
2126:
2125:
2121:
2100:
2096:
2087:
2083:
2072:
2070:
2067:
2066:
2046:
2042:
2013:
2010:
2009:
1976:) are at least
1801:
1790:
1779:
1760:
1753:
1746:
1731:
1724:
1711:, the sequence
1705:
1682:
1676:
1656:
1637:
1583:
1514:
1503:
1496:
1481:
1470:
1451:
1444:
1428:
1405:
1371:
1367:
1365:
1362:
1361:
1342:
1327:
1323:
1315:
1312:
1311:
1295:
1287:
1284:
1283:
1253:
1239:
1237:
1235:
1232:
1231:
1210:
1173:
1169:
1164:
1157:
1153:
1145:
1131:
1128:
1127:
1098:
1083:
1079:
1062:
1059:
1058:
1029:
1003:
1000:
999:
959:
953:
949:
941:
938:
937:
903:
899:
891:
885:
881:
864:
861:
860:
838:
823:
819:
811:
808:
807:
782:
769:
760:
750:
748:
740:
737:
736:
674:
661:
657:
652:
641:
638:
637:
611:
597:
592:
589:
588:
565:
548:
545:
544:
531:in expectation.
510:
493:
490:
489:
464:
458:
451:
431:
428:
427:
406:
392:
390:
377:
372:
359:
357:
354:
353:
330:
313:
310:
309:
290:
279:
276:
275:
250:
247:
246:
222:
214:
58:The associated
12:
11:
5:
5798:
5788:
5787:
5771:
5770:
5729:
5722:
5700:
5668:
5627:
5578:
5571:
5546:
5539:
5514:
5507:
5485:
5436:
5415:(2): 181–203.
5395:
5388:
5366:
5339:
5297:
5290:
5260:
5241:(5): 281–287.
5219:
5200:(4): 149–154.
5175:
5146:(1): 116–127.
5123:
5094:(1): 144–162.
5071:
5065:978-0716710448
5064:
5038:
5011:(1): 125–139.
4991:
4950:
4931:(2): 190–196.
4911:
4870:
4838:(2009-07-11).
4824:
4818:
4771:
4752:(2): 416–429.
4740:(1969-03-01).
4738:Graham, Ron L.
4725:
4724:
4722:
4719:
4718:
4717:
4705:
4702:
4685:
4682:
4660:
4657:
4656:
4655:
4648:
4637:
4636:
4633:
4625:
4618:
4607:
4580:
4577:
4576:
4575:
4574:
4573:
4567:
4562:
4557:
4552:
4547:
4542:
4506:
4458:
4455:
4431:
4428:
4413:
4378:
4365:memory, where
4331:
4328:
4310:
4289:
4288:
4284:
4281:
4268:
4265:
4262:
4259:
4256:
4253:
4250:
4247:
4244:
4241:
4238:
4235:
4232:
4229:
4226:
4221:
4218:
4213:
4210:
4207:
4183:
4180:
4176:
4172:
4169:
4166:
4163:
4152:
4151:
4133:
4130:
4125:
4120:
4115:
4111:
4107:
4102:
4098:
4094:
4089:
4086:
4081:
4078:
4073:
4068:
4064:
4057:
4054:
4051:
4047:
4032:
4021:
4008:
3994:
3991:
3986:
3981:
3977:
3971:
3967:
3964:
3961:
3955:
3950:
3945:
3941:
3937:
3932:
3929:
3924:
3919:
3915:
3901:
3886:
3860:
3857:
3834:
3831:
3827:
3794:
3791:
3788:
3785:
3780:
3776:
3772:
3767:
3764:
3760:
3737:
3734:
3730:
3718:
3717:
3705:
3702:
3696:
3691:
3679:
3666:
3662:
3658:
3654:
3648:
3643:
3637:
3634:
3630:
3625:
3613:
3601:
3598:
3592:
3587:
3581:
3578:
3574:
3569:
3557:
3546:
3543:
3539:
3535:
3532:
3529:
3526:
3523:
3517:
3512:
3506:
3503:
3499:
3494:
3476:
3464:
3449:
3446:
3440:for any fixed
3425:
3420:
3417:
3413:
3409:
3402:
3398:
3393:
3389:
3386:
3383:
3380:
3352:
3348:
3343:
3317:
3313:
3309:
3289:
3288:
3268:
3265:
3262:
3242:
3239:
3235:
3231:
3227:
3223:
3220:
3217:
3214:
3211:
3208:
3205:
3202:
3199:
3196:
3193:
3189:
3185:
3182:
3179:
3176:
3173:
3168:
3165:
3161:
3157:
3153:
3149:
3145:
3140:
3136:
3133:
3129:
3125:
3122:
3119:
3116:
3113:
3110:
3100:
3088:
3085:
3082:
3078:
3074:
3071:
3068:
3065:
3062:
3059:
3049:
3037:
3033:
3029:
3026:
3004:
3000:
2996:
2993:
2990:
2987:
2983:
2979:
2976:
2973:
2970:
2966:
2960:
2956:
2935:
2932:
2928:
2924:
2921:
2918:
2915:
2912:
2909:
2905:
2901:
2898:
2895:
2892:
2889:
2886:
2876:
2864:
2861:
2858:
2854:
2850:
2847:
2844:
2841:
2838:
2835:
2794:
2787:
2783:
2778:
2774:
2771:
2768:
2763:
2760:
2757:
2753:
2749:
2744:
2740:
2736:
2733:
2729:
2715:
2697:
2693:
2689:
2686:
2683:
2680:
2677:
2674:
2662:
2659:
2625:
2622:
2618:
2614:
2610:
2606:
2602:
2579:
2576:
2572:
2568:
2563:
2560:
2555:
2550:
2546:
2542:
2514:
2510:
2506:
2503:
2500:
2496:
2492:
2489:
2486:
2483:
2479:
2473:
2469:
2447:
2426:
2406:
2401:
2397:
2392:
2388:
2385:
2382:
2379:
2374:
2370:
2362:
2358:
2352:
2349:
2346:
2342:
2338:
2335:
2331:
2327:
2324:
2294:
2290:
2269:
2262:
2258:
2253:
2249:
2246:
2243:
2238:
2235:
2232:
2228:
2224:
2219:
2215:
2211:
2208:
2204:
2165:
2161:
2140:
2133:
2129:
2124:
2120:
2117:
2114:
2109:
2106:
2103:
2099:
2095:
2090:
2086:
2082:
2079:
2075:
2054:
2049:
2045:
2041:
2038:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
1986:
1985:
1946:
1859:
1858:
1845:, then 52 new
1807:
1799:
1788:
1777:
1758:
1751:
1744:
1741:. Note that
1729:
1722:
1703:
1680:
1674:
1664:input rounding
1660:
1659:
1654:
1635:
1618:
1581:
1568:
1567:
1557:
1512:
1501:
1494:
1479:
1468:
1457:between 1 and
1449:
1443:
1440:
1426:
1404:
1401:
1400:
1399:
1396:
1374:
1370:
1349:
1345:
1341:
1338:
1335:
1330:
1326:
1322:
1319:
1298:
1294:
1291:
1280:
1265:
1262:
1259:
1256:
1251:
1248:
1245:
1242:
1209:
1206:
1205:
1204:
1203:
1202:
1186:
1181:
1176:
1172:
1167:
1163:
1160:
1156:
1152:
1148:
1144:
1141:
1138:
1135:
1120:
1108:
1105:
1101:
1097:
1094:
1091:
1086:
1082:
1078:
1075:
1072:
1069:
1066:
1051:
1039:
1036:
1032:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
985:
969:
966:
962:
956:
952:
948:
945:
932:is fixed. For
917:
912:
909:
906:
902:
898:
894:
888:
884:
880:
877:
874:
871:
868:
857:
845:
841:
837:
834:
831:
826:
822:
818:
815:
792:
789:
785:
781:
778:
775:
772:
767:
763:
759:
756:
753:
747:
744:
713:
712:
695:
681:
677:
673:
670:
667:
664:
660:
655:
651:
648:
645:
621:
618:
614:
610:
607:
604:
600:
596:
572:
568:
564:
561:
558:
555:
552:
532:
520:
517:
513:
509:
506:
503:
500:
497:
474:
471:
467:
461:
457:
454:
450:
447:
444:
441:
438:
435:
412:
409:
404:
401:
398:
395:
389:
383:
380:
376:
371:
366:
363:
337:
333:
329:
326:
323:
320:
317:
297:
293:
289:
286:
283:
263:
260:
257:
254:
221:
218:
213:
210:
209:
208:
201:
170:
163:
134:
133:
114:
95:
9:
6:
4:
3:
2:
5797:
5786:
5783:
5782:
5780:
5766:
5762:
5757:
5752:
5748:
5744:
5740:
5733:
5725:
5719:
5715:
5711:
5704:
5696:
5690:
5679:
5672:
5664:
5660:
5655:
5650:
5646:
5642:
5638:
5631:
5623:
5619:
5615:
5611:
5606:
5601:
5597:
5593:
5589:
5582:
5574:
5568:
5564:
5557:
5550:
5542:
5536:
5532:
5525:
5518:
5510:
5504:
5500:
5496:
5489:
5481:
5477:
5473:
5469:
5464:
5459:
5455:
5451:
5447:
5440:
5432:
5428:
5423:
5418:
5414:
5410:
5406:
5399:
5391:
5385:
5381:
5377:
5370:
5362:
5355:
5354:
5346:
5344:
5335:
5331:
5327:
5323:
5319:
5315:
5311:
5304:
5302:
5293:
5287:
5283:
5279:
5275:
5271:
5264:
5256:
5252:
5248:
5244:
5240:
5236:
5235:
5230:
5223:
5215:
5211:
5207:
5203:
5199:
5195:
5194:
5189:
5182:
5180:
5171:
5167:
5163:
5159:
5154:
5149:
5145:
5141:
5137:
5130:
5128:
5119:
5115:
5111:
5107:
5102:
5097:
5093:
5089:
5085:
5078:
5076:
5067:
5061:
5057:
5052:
5051:
5042:
5034:
5030:
5026:
5022:
5018:
5014:
5010:
5006:
5002:
4995:
4987:
4983:
4978:
4973:
4969:
4965:
4961:
4954:
4946:
4942:
4938:
4934:
4930:
4926:
4922:
4915:
4907:
4903:
4899:
4895:
4891:
4887:
4886:
4881:
4874:
4856:
4852:
4848:
4841:
4837:
4831:
4829:
4821:
4815:
4811:
4807:
4802:
4797:
4793:
4789:
4785:
4778:
4776:
4767:
4763:
4759:
4755:
4751:
4747:
4743:
4739:
4733:
4731:
4726:
4715:
4714:prtpy package
4711:
4708:
4707:
4701:
4699:
4695:
4691:
4681:
4679:
4674:
4672:
4668:
4667:
4653:
4649:
4646:
4642:
4641:
4640:
4634:
4631:
4624:
4617:
4613:
4606:
4602:
4598:
4594:
4593:
4592:
4590:
4589:binary search
4586:
4571:
4568:
4566:
4563:
4561:
4558:
4556:
4553:
4551:
4548:
4546:
4543:
4540:
4536:
4532:
4528:
4525:uses CKK for
4524:
4521:
4520:
4518:
4514:
4510:
4507:
4504:
4500:
4496:
4492:
4488:
4484:
4480:
4476:
4472:
4456:
4453:
4445:
4429:
4426:
4418:
4414:
4411:
4407:
4403:
4399:
4395:
4391:
4387:
4383:
4379:
4376:
4372:
4362:
4358:
4354:
4350:
4345:
4341:
4340:
4339:
4337:
4327:
4325:
4321:
4317:
4313:
4306:
4302:
4298:
4294:
4287:
4286:
4280:
4266:
4263:
4260:
4257:
4251:
4248:
4245:
4239:
4236:
4233:
4230:
4227:
4219:
4216:
4211:
4208:
4197:
4178:
4174:
4170:
4164:
4161:
4149:
4131:
4128:
4123:
4113:
4109:
4105:
4100:
4096:
4092:
4087:
4084:
4079:
4076:
4066:
4062:
4055:
4052:
4049:
4045:
4035:
4028:
4024:
4017:
4013:
4009:
3992:
3989:
3984:
3979:
3975:
3969:
3965:
3962:
3959:
3953:
3943:
3939:
3935:
3930:
3927:
3922:
3917:
3913:
3904:
3897:
3893:
3889:
3882:
3878:
3877:
3876:
3874:
3870:
3866:
3856:
3854:
3850:
3832:
3829:
3825:
3816:
3813:. Therefore,
3812:
3808:
3792:
3789:
3786:
3783:
3778:
3774:
3770:
3765:
3762:
3758:
3735:
3732:
3728:
3703:
3700:
3689:
3680:
3660:
3652:
3641:
3635:
3632:
3623:
3614:
3599:
3596:
3585:
3579:
3576:
3567:
3558:
3530:
3524:
3521:
3510:
3504:
3501:
3492:
3483:
3482:
3481:
3479:
3472:
3467:
3463:
3459:
3455:
3445:
3443:
3439:
3418:
3415:
3411:
3407:
3400:
3396:
3391:
3387:
3384:
3378:
3370:
3350:
3346:
3341:
3332:
3311:
3298:
3294:
3286:
3282:
3266:
3263:
3260:
3229:
3221:
3218:
3215:
3212:
3206:
3203:
3200:
3197:
3180:
3174:
3166:
3163:
3155:
3147:
3134:
3123:
3120:
3114:
3111:
3108:
3101:
3083:
3072:
3069:
3063:
3060:
3057:
3050:
3024:
2998:
2994:
2991:
2974:
2971:
2968:
2964:
2954:
2919:
2913:
2910:
2899:
2896:
2890:
2887:
2884:
2877:
2862:
2859:
2848:
2845:
2839:
2836:
2833:
2826:
2825:
2824:
2822:
2817:
2816:
2812:
2808:
2785:
2781:
2776:
2772:
2769:
2766:
2761:
2758:
2755:
2751:
2747:
2742:
2738:
2731:
2718:
2711:
2687:
2684:
2678:
2675:
2672:
2658:
2656:
2652:
2648:
2644:
2639:
2623:
2620:
2616:
2612:
2604:
2577:
2574:
2570:
2566:
2561:
2558:
2548:
2544:
2530:
2508:
2504:
2501:
2487:
2484:
2481:
2477:
2467:
2424:
2399:
2395:
2390:
2386:
2383:
2377:
2372:
2368:
2360:
2356:
2350:
2347:
2344:
2340:
2336:
2322:
2314:
2310:
2292:
2288:
2260:
2256:
2251:
2247:
2244:
2241:
2236:
2233:
2230:
2226:
2222:
2217:
2213:
2206:
2193:
2189:
2185:
2181:
2163:
2159:
2131:
2127:
2122:
2118:
2115:
2112:
2107:
2104:
2101:
2097:
2093:
2088:
2084:
2077:
2047:
2043:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2007:
2003:
1999:
1995:
1991:
1983:
1979:
1975:
1971:
1967:
1963:
1959:
1955:
1951:
1947:
1944:
1940:
1936:
1932:
1928:
1924:
1920:
1916:
1912:
1908:
1904:
1900:
1896:
1892:
1888:
1887:
1886:
1884:
1880:
1876:
1872:
1868:
1864:
1856:
1852:
1848:
1844:
1840:
1836:
1832:
1828:
1824:
1820:
1816:
1812:
1808:
1806:
1802:
1795:
1791:
1784:
1780:
1773:
1769:
1765:
1761:
1754:
1747:
1740:
1736:
1732:
1725:
1718:
1714:
1710:
1706:
1699:
1698:
1697:
1695:
1691:
1687:
1683:
1673:
1669:
1665:
1657:
1650:
1646:
1642:
1638:
1631:
1627:
1623:
1619:
1616:
1612:
1608:
1604:
1600:
1596:
1592:
1588:
1587:
1586:
1584:
1577:
1573:
1565:
1561:
1558:
1555:
1551:
1547:
1543:
1539:
1535:
1531:
1527:
1523:
1522:
1521:
1519:
1515:
1508:
1504:
1497:
1490:
1486:
1482:
1475:
1471:
1464:
1460:
1456:
1452:
1439:
1437:
1433:
1429:
1422:
1418:
1414:
1410:
1397:
1394:
1390:
1372:
1368:
1343:
1339:
1336:
1333:
1328:
1324:
1317:
1296:
1292:
1289:
1281:
1263:
1260:
1257:
1254:
1249:
1246:
1243:
1240:
1229:
1225:
1221:
1220:
1215:
1214:
1213:
1200:
1174:
1170:
1165:
1161:
1150:
1146:
1142:
1133:
1125:
1121:
1099:
1095:
1092:
1089:
1084:
1080:
1076:
1070:
1064:
1056:
1052:
1030:
1026:
1023:
1020:
1017:
1011:
1005:
997:
993:
992:
990:
986:
983:
964:
960:
954:
950:
943:
935:
931:
910:
907:
904:
896:
892:
886:
882:
875:
872:
866:
858:
839:
835:
832:
829:
824:
820:
813:
787:
783:
779:
773:
770:
765:
761:
757:
754:
751:
745:
742:
734:
730:
727:, choose the
726:
722:
721:
720:
718:
710:
706:
702:
701:
696:
675:
671:
668:
658:
653:
649:
646:
643:
635:
619:
616:
612:
608:
605:
602:
598:
594:
586:
566:
562:
559:
556:
550:
542:
538:
537:
533:
515:
511:
507:
501:
498:
495:
487:
486:almost surely
469:
465:
459:
455:
452:
448:
445:
439:
436:
433:
410:
407:
402:
399:
396:
393:
387:
381:
378:
374:
369:
364:
361:
351:
331:
327:
324:
321:
315:
295:
291:
287:
284:
281:
258:
252:
244:
240:
239:
235:
234:
233:
231:
227:
217:
206:
202:
199:
195:
191:
187:
183:
179:
175:
171:
168:
164:
161:
157:
156:
155:
152:
150:
145:
143:
139:
131:
127:
123:
122:maximin share
119:
115:
112:
108:
104:
100:
96:
93:
92:
91:
89:
85:
81:
77:
73:
69:
65:
61:
56:
54:
50:
46:
44:
40:, and called
39:
35:
31:
30:Ronald Graham
27:
23:
19:
5746:
5742:
5732:
5713:
5703:
5671:
5644:
5640:
5630:
5595:
5591:
5581:
5562:
5549:
5530:
5517:
5498:
5488:
5453:
5449:
5439:
5412:
5408:
5398:
5379:
5369:
5352:
5320:(1): 55–66.
5317:
5313:
5273:
5263:
5238:
5232:
5222:
5197:
5191:
5143:
5139:
5091:
5087:
5049:
5041:
5008:
5004:
4994:
4967:
4963:
4953:
4928:
4924:
4914:
4892:(1): 74–87.
4889:
4883:
4873:
4862:. Retrieved
4846:
4791:
4749:
4745:
4709:
4697:
4693:
4687:
4684:Applications
4677:
4675:
4670:
4664:
4662:
4651:
4644:
4638:
4629:
4622:
4615:
4611:
4604:
4600:
4596:
4582:
4569:
4564:
4559:
4554:
4549:
4544:
4541:into halves.
4538:
4534:
4530:
4529:=2, but for
4526:
4522:
4508:
4502:
4494:
4486:
4482:
4478:
4470:
4443:
4416:
4405:
4401:
4393:
4385:
4381:
4374:
4373:=2, or when
4370:
4360:
4356:
4352:
4348:
4333:
4319:
4308:
4304:
4300:
4296:
4295:) = 2, or f(
4292:
4290:
4195:
4153:
4147:
4030:
4026:
4019:
4018:) with sums
4015:
4011:
3899:
3898:) with sums
3895:
3891:
3884:
3880:
3872:
3868:
3864:
3862:
3852:
3848:
3810:
3806:
3719:
3474:
3470:
3465:
3461:
3457:
3453:
3451:
3441:
3437:
3368:
3330:
3296:
3292:
3290:
3284:
3280:
2818:
2814:
2810:
2806:
2713:
2709:
2664:
2650:
2646:
2642:
2640:
2528:
2417:. Denote by
2312:
2308:
2191:
2187:
2183:
2179:
2005:
2001:
1997:
1993:
1989:
1987:
1981:
1977:
1973:
1969:
1965:
1961:
1957:
1953:
1949:
1942:
1938:
1934:
1930:
1926:
1922:
1918:
1914:
1910:
1909:is at least
1906:
1902:
1898:
1894:
1890:
1882:
1878:
1874:
1870:
1866:
1862:
1860:
1854:
1850:
1846:
1842:
1838:
1834:
1830:
1826:
1822:
1818:
1814:
1810:
1804:
1797:
1793:
1786:
1782:
1775:
1771:
1767:
1763:
1756:
1749:
1742:
1738:
1734:
1727:
1720:
1716:
1712:
1708:
1701:
1693:
1689:
1685:
1678:
1671:
1667:
1663:
1661:
1652:
1648:
1644:
1640:
1633:
1629:
1625:
1621:
1614:
1610:
1606:
1602:
1601:is at least
1598:
1594:
1590:
1579:
1575:
1571:
1569:
1553:
1549:
1545:
1541:
1537:
1533:
1529:
1526:Condition F*
1525:
1517:
1510:
1506:
1499:
1492:
1488:
1484:
1477:
1473:
1466:
1462:
1458:
1454:
1447:
1445:
1435:
1431:
1424:
1420:
1416:
1412:
1408:
1406:
1227:
1223:
1217:
1211:
1197:. This is a
1123:
1054:
995:
988:
981:
933:
929:
732:
728:
724:
714:
708:
698:
633:
584:
540:
535:
349:
242:
236:
225:
223:
215:
197:
193:
189:
185:
181:
177:
153:
146:
141:
137:
135:
129:
125:
106:
102:
101:. There are
87:
83:
79:
71:
67:
63:
57:
52:
48:
42:
41:
37:
21:
15:
5643:. AAAI'14.
5598:: 144–152.
4836:Walsh, Toby
4632:+1 numbers.
4398:depth-first
3559:subject to
3287:-1 subsets.
705:bin packing
4864:2021-10-05
4721:References
4334:There are
4029:with sums
3883:with sums
2186:inputs in
1540:, then |f(
1483:)), where
5765:0307-904X
5614:2334-0843
5472:0004-5411
5431:0004-3702
5334:1099-1425
5255:0167-6377
5214:0167-6377
5162:0004-5411
5110:0004-5411
5025:1613-9178
4970:: 71–72.
4945:0196-5212
4906:0364-765X
4766:0036-1399
4690:elections
4258:⋅
4252:ϵ
4240:≤
4228:⋅
4217:ϵ
4182:⌉
4179:δ
4168:⌈
4119:#
4106:≤
4093:≤
4077:−
4072:#
3954:≤
3949:#
3936:≤
3923:−
3784:−
3701:≥
3653:⋅
3633:∈
3624:∑
3577:∈
3568:∑
3522:⋅
3502:∈
3493:∑
3484:Minimize
3408:⋅
3388:⋅
3291:For each
3264:≥
3230:−
3216:−
3164:∈
3148:≤
3087:∞
3003:#
2959:#
2770:…
2613:≤
2513:#
2472:#
2378:⋅
2341:∑
2245:…
2116:…
2037:…
2004:, where
1726:which is
1647:in 1,...,
1564:concavity
1560:Convexity
1411:in 1,...,
1373:ε
1340:
1329:ε
1297:ε
1293:−
1261:−
1247:−
1230:=2, and
1171:ε
1151:ε
1096:
1027:
965:ϵ
908:−
897:ϵ
876:⋅
836:
791:⌋
777:⌊
755:−
672:
663:Θ
606:−
563:
456:
449:
400:−
370:−
328:
285:−
5779:Category
5689:cite web
5622:12458816
5480:63854223
5170:10956951
5033:17222989
4986:45875088
4855:Archived
4790:(eds.),
4659:Variants
4515:and the
4493:s; with
4390:ary tree
4036:, where
3905:, where
3367:, where
3253:for all
2813:/2 and 2
2280:, where
2151:, where
1960:/2 and 2
1913:. Since
1770:, and
1700:For any
1643:for all
1632:/2 <
1624:/2 and 2
1432:weighted
1360:, where
1310:in time
1122:For any
1053:For any
994:For any
715:Several
352:=2, and
111:makespan
26:multiset
5663:8594071
5118:9739129
4806:Bibcode
4710:Python:
4663:In the
4481:=2 and
2665:Define
1885:) too:
1841:is 51.3
1785:, so
1548:)|<ε
149:NP-hard
5763:
5720:
5661:
5620:
5612:
5569:
5537:
5505:
5478:
5470:
5429:
5386:
5332:
5288:
5253:
5212:
5168:
5160:
5116:
5108:
5062:
5031:
5023:
4984:
4943:
4904:
4816:
4764:
4614:, and
4346:takes
1792:< (
1639:< 2
1536:|<δ
725:r>0
488:, and
5681:(PDF)
5659:S2CID
5618:S2CID
5559:(PDF)
5527:(PDF)
5476:S2CID
5361:IJCAI
5357:(PDF)
5166:S2CID
5114:S2CID
5029:S2CID
4982:S2CID
4858:(PDF)
4843:(PDF)
4796:arXiv
2592:, so
2459:with
1774:<
1755:<
1707:>
1677:,...,
1453:(for
82:into
5761:ISSN
5718:ISBN
5695:link
5610:ISSN
5567:ISBN
5535:ISBN
5503:ISBN
5468:ISSN
5427:ISSN
5384:ISBN
5330:ISSN
5286:ISBN
5251:ISSN
5210:ISSN
5158:ISSN
5106:ISSN
5060:ISBN
5021:ISSN
4941:ISSN
4902:ISSN
4814:ISBN
4762:ISSN
4712:The
4583:The
4415:The
4380:The
4359:− 1)
4342:The
4316:P=NP
3681:and
3615:and
3295:and
2992:<
2972:<
2502:<
2485:<
1889:Let
1589:Let
1544:)-f(
1446:Let
1391:for
1216:For
1199:PTAS
697:The
224:The
203:The
172:The
165:The
158:The
144:≥3.
5751:doi
5649:doi
5600:doi
5458:doi
5417:doi
5413:106
5322:doi
5278:doi
5243:doi
5202:doi
5148:doi
5096:doi
5056:238
5013:doi
4972:doi
4933:doi
4894:doi
4754:doi
4673:).
4626:k+1
4299:)=(
3855:).
3456:in
3139:min
2946:if
2638:.
1861:In
1857:)).
1847:L/d
1843:L/d
1835:L/d
1831:L/d
1819:L/d
1796:+1)
1772:L/d
1709:L/d
1668:S =
1438:).
1337:log
1093:log
1024:log
833:log
669:log
560:log
453:log
446:log
325:log
53:k*T
16:In
5781::
5759:.
5747:37
5745:.
5741:.
5712:.
5691:}}
5687:{{
5657:.
5645:28
5639:.
5616:.
5608:.
5596:23
5594:.
5590:.
5561:.
5529:.
5497:.
5474:.
5466:.
5454:65
5452:.
5448:.
5425:.
5411:.
5407:.
5378:.
5359:.
5342:^
5328:.
5316:.
5312:.
5300:^
5284:.
5249:.
5239:11
5237:.
5231:.
5208:.
5198:20
5196:.
5190:.
5178:^
5164:.
5156:.
5144:23
5142:.
5138:.
5126:^
5112:.
5104:.
5092:34
5090:.
5086:.
5074:^
5058:.
5027:.
5019:.
5009:21
5007:.
5003:.
4980:.
4966:.
4962:.
4939:.
4927:.
4923:.
4900:.
4888:.
4882:.
4827:^
4812:,
4804:,
4774:^
4760:.
4750:17
4748:.
4744:.
4729:^
4680:.
4621:+
4599:)/
4326:.
4165::=
4150:).
3875:.
3809:,
3444:.
2823::
2815:L.
2309:hL
2180:hL
1998:hL
1984:).
1962:L.
1805:d.
1748:≤
1556:).
232:.
55:.
20:,
5767:.
5753::
5726:.
5697:)
5683:.
5665:.
5651::
5624:.
5602::
5575:.
5543:.
5511:.
5482:.
5460::
5433:.
5419::
5392:.
5363:.
5336:.
5324::
5318:1
5294:.
5280::
5257:.
5245::
5216:.
5204::
5172:.
5150::
5120:.
5098::
5068:.
5035:.
5015::
4988:.
4974::
4968:1
4947:.
4935::
4929:3
4908:.
4896::
4890:6
4867:.
4808::
4798::
4768:.
4756::
4698:k
4694:k
4652:k
4645:k
4630:k
4623:s
4619:k
4616:s
4612:S
4608:1
4605:s
4601:k
4597:S
4572:.
4539:k
4535:S
4531:k
4527:k
4503:k
4495:k
4487:k
4483:k
4479:k
4471:k
4457:!
4454:k
4444:k
4430:!
4427:k
4406:k
4402:n
4394:k
4388:-
4386:k
4375:k
4371:k
4367:m
4363:)
4361:m
4357:k
4355:(
4353:n
4351:(
4349:O
4320:x
4311:i
4309:C
4307:(
4305:f
4301:x
4297:x
4293:x
4267:T
4264:P
4261:O
4255:)
4249:+
4246:1
4243:(
4237:T
4234:P
4231:O
4225:)
4220:3
4212:+
4209:1
4206:(
4196:S
4175:/
4171:5
4162:d
4148:n
4132:d
4129:L
4124:+
4114:i
4110:C
4101:i
4097:C
4088:d
4085:L
4080:2
4067:i
4063:C
4056:1
4053:+
4050:d
4046:d
4033:i
4031:C
4027:S
4022:i
4020:C
4016:d
4014:(
4012:S
4007:.
3993:d
3990:L
3985:+
3980:i
3976:C
3970:d
3966:1
3963:+
3960:d
3944:i
3940:C
3931:d
3928:L
3918:i
3914:C
3902:i
3900:C
3896:d
3894:(
3892:S
3887:i
3885:C
3881:S
3873:S
3869:d
3867:(
3865:S
3853:n
3849:n
3833:d
3830:4
3826:d
3811:k
3807:n
3793:2
3790:+
3787:d
3779:2
3775:d
3771:+
3766:d
3763:4
3759:d
3736:d
3733:4
3729:d
3716:.
3704:0
3695:t
3690:x
3665:n
3661:=
3657:t
3647:t
3642:x
3636:T
3629:t
3600:k
3597:=
3591:t
3586:x
3580:T
3573:t
3545:)
3542:)
3538:t
3534:(
3531:C
3528:(
3525:f
3516:t
3511:x
3505:T
3498:t
3477:i
3475:C
3473:(
3471:f
3466:t
3462:x
3458:T
3454:t
3442:d
3438:n
3424:)
3419:d
3416:4
3412:d
3401:2
3397:d
3392:n
3385:k
3382:(
3379:O
3369:n
3351:2
3347:d
3342:n
3331:n
3316:|
3312:T
3308:|
3297:n
3293:k
3285:k
3281:k
3267:2
3261:k
3241:]
3238:)
3234:t
3226:n
3222:,
3219:1
3213:k
3210:(
3207:L
3204:A
3201:V
3198:+
3195:)
3192:)
3188:t
3184:(
3181:C
3178:(
3175:f
3172:[
3167:T
3160:t
3156:,
3152:n
3144:t
3135:=
3132:)
3128:n
3124:,
3121:k
3118:(
3115:L
3112:A
3109:V
3084:=
3081:)
3077:n
3073:,
3070:1
3067:(
3064:L
3061:A
3058:V
3048:.
3036:)
3032:n
3028:(
3025:C
2999:L
2995:2
2989:)
2986:)
2982:n
2978:(
2975:C
2969:2
2965:/
2955:L
2934:)
2931:)
2927:n
2923:(
2920:C
2917:(
2914:f
2911:=
2908:)
2904:n
2900:,
2897:1
2894:(
2891:L
2888:A
2885:V
2863:0
2860:=
2857:)
2853:0
2849:,
2846:0
2843:(
2840:L
2837:A
2834:V
2811:L
2807:k
2793:)
2786:2
2782:d
2777:n
2773:,
2767:,
2762:1
2759:+
2756:d
2752:n
2748:,
2743:d
2739:n
2735:(
2732:=
2728:n
2716:i
2714:C
2712:(
2710:f
2696:)
2692:n
2688:,
2685:k
2682:(
2679:L
2676:A
2673:V
2651:d
2647:d
2645:(
2643:S
2624:d
2621:4
2617:d
2609:|
2605:T
2601:|
2578:d
2575:4
2571:d
2567:=
2562:d
2559:2
2554:)
2549:2
2545:d
2541:(
2529:d
2509:L
2505:2
2499:)
2495:t
2491:(
2488:C
2482:2
2478:/
2468:L
2446:t
2425:T
2405:)
2400:2
2396:d
2391:/
2387:L
2384:h
2381:(
2373:h
2369:t
2361:2
2357:d
2351:d
2348:=
2345:h
2337:=
2334:)
2330:t
2326:(
2323:C
2313:d
2311:/
2293:h
2289:x
2268:)
2261:2
2257:d
2252:t
2248:,
2242:,
2237:1
2234:+
2231:d
2227:t
2223:,
2218:d
2214:t
2210:(
2207:=
2203:t
2192:d
2190:(
2188:S
2184:d
2182:/
2164:h
2160:n
2139:)
2132:2
2128:d
2123:n
2119:,
2113:,
2108:1
2105:+
2102:d
2098:n
2094:,
2089:d
2085:n
2081:(
2078:=
2074:n
2053:)
2048:2
2044:d
2040:,
2034:,
2031:1
2028:+
2025:d
2022:,
2019:d
2016:(
2006:h
2002:d
2000:/
1994:d
1992:(
1990:S
1982:d
1980:/
1978:L
1974:d
1972:(
1970:S
1966:d
1958:L
1954:d
1952:(
1950:S
1943:L
1939:d
1937:(
1935:S
1931:L
1927:L
1923:d
1921:/
1919:L
1915:L
1911:L
1907:L
1903:d
1901:(
1899:S
1895:k
1891:L
1883:d
1881:(
1879:S
1875:d
1873:/
1871:L
1867:d
1865:(
1863:S
1855:d
1853:(
1851:S
1839:S
1827:d
1825:(
1823:S
1815:d
1813:(
1811:S
1803:/
1800:j
1798:v
1794:d
1789:j
1787:v
1783:d
1781:/
1778:j
1776:v
1768:d
1766:/
1764:L
1762:+
1759:j
1757:v
1752:j
1750:v
1745:j
1743:v
1739:d
1737:/
1735:L
1730:j
1728:v
1723:j
1721:v
1717:d
1715:(
1713:S
1704:j
1702:v
1694:d
1692:(
1690:S
1686:d
1681:n
1679:v
1675:1
1672:v
1670:(
1655:i
1653:C
1649:k
1645:i
1641:L
1636:i
1634:C
1630:L
1628:(
1626:L
1622:L
1617:.
1615:L
1611:f
1607:x
1603:L
1599:x
1595:k
1591:L
1582:i
1580:C
1578:(
1576:f
1572:n
1554:x
1552:(
1550:f
1546:x
1542:y
1538:x
1534:x
1532:-
1530:y
1518:f
1513:i
1511:C
1509:(
1507:f
1502:i
1500:C
1495:i
1493:C
1491:(
1489:f
1485:f
1480:i
1478:C
1476:(
1474:f
1469:i
1467:C
1463:i
1459:k
1455:i
1450:i
1448:C
1436:n
1427:i
1425:w
1421:i
1417:i
1413:k
1409:i
1395:.
1369:c
1348:)
1344:k
1334:n
1325:c
1321:(
1318:O
1290:1
1264:2
1258:k
1255:4
1250:1
1244:k
1241:3
1228:k
1224:k
1201:.
1185:)
1180:)
1175:2
1166:/
1162:1
1159:(
1155:)
1147:/
1143:n
1140:(
1137:(
1134:O
1124:ε
1119:.
1107:)
1104:)
1100:n
1090:+
1085:4
1081:k
1077:r
1074:(
1071:n
1068:(
1065:O
1055:r
1050:.
1038:)
1035:)
1031:n
1021:+
1018:r
1015:(
1012:n
1009:(
1006:O
996:r
989:k
984:.
968:)
961:/
955:2
951:n
947:(
944:O
934:k
930:k
916:)
911:1
905:k
901:)
893:/
887:2
883:n
879:(
873:n
870:(
867:O
856:.
844:)
840:n
830:n
825:r
821:2
817:(
814:O
788:k
784:/
780:r
774:+
771:1
766:k
762:/
758:1
752:1
746:+
743:1
733:S
729:r
709:k
680:)
676:n
666:(
659:n
654:/
650:1
647:+
644:1
634:k
620:k
617:3
613:/
609:1
603:3
599:/
595:4
585:k
571:)
567:n
557:n
554:(
551:O
519:)
516:n
512:/
508:1
505:(
502:O
499:+
496:1
473:)
470:n
466:/
460:n
443:(
440:O
437:+
434:1
411:k
408:3
403:1
397:k
394:4
388:=
382:k
379:3
375:1
365:3
362:4
350:k
336:)
332:n
322:n
319:(
316:O
296:k
292:/
288:1
282:2
262:)
259:n
256:(
253:O
200:.
198:d
194:k
190:k
186:d
182:k
178:k
142:k
138:k
130:S
126:k
107:S
103:k
88:k
84:k
80:S
72:T
68:k
64:S
49:S
43:k
38:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.