Content deleted Content added
Erel Segal (talk | contribs) |
m Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published) |
||
Line 10:
=== Two-way partitioning ===
For ''k''=2, the main step (2) works as follows.
* Take the two largest numbers in ''S'', remove them from ''S'', and insert their difference (this represents a decision to put each of these numbers in a different subset).
* Proceed in this way until a single number remains. This single number is the difference in sums between the two subsets.
For example, if S = {8,7,6,5,4}, then the resulting difference-sets are 6,5,4,1, then 4,1,1, then 3,1 then 2.
Step 3 constructs the subsets in the partition by backtracking. The last step corresponds to {2},{}. Then 2 is replaced by 3 in one set and 1 in the other set: {3},{1}, then {4},{1,1}, then {4,5}, {1,6}, then {4,7,5}, {8,6}, where the sum-difference is indeed 2.
The runtime complexity of this algorithm is dominated by the step 1 (sorting), which takes O(''n'' log ''n'').
Note that this partition is not optimal: in the partition {8,7}, {6,5,4} the sum-difference is 0. However, there is evidence that it provides a "good" partition:
* If the numbers are uniformly distributed in [0,1], then the expected difference between the two sums is <math>n^{-\Theta(\log(n)))}</math>. This also implies that the expected ratio between the maximum sum and the optimal maximum sum is <math>1+n^{-\Theta(\log(n)))}</math> .
* When there are at most 4 items, LDM returns the optimal partition.
*LDM always returns a partition in which the largest sum is at most 7/6 times the optimum.<ref>{{Cite journal|last1=Fischetti|first1=Matteo|last2=Martello|first2=Silvano|date=1987-02-01|title=Worst-case analysis of the differencing method for the partition problem|url=https://doi.org/10.1007/BF02591687|journal=Mathematical Programming|language=en|volume=37|issue=1|pages=117–120|doi=10.1007/BF02591687|issn=1436-4646}}</ref> This is tight when there are 5 or more items.'''<ref name=":2" />'''
Line 29:
=== Multi-way partitioning ===
For any ''k'' ≥ 2, the algorithm can be generalized in the following way.'''<ref name=":2" />'''
* Initially, for each number ''i'' in ''S'', construct a ''k''-tuple of subsets, in which one subset is {''i''} and the other ''k''-1 subsets are empty.
Line 48:
*When the number of items ''n'' is between ''k''+2 and 2''k'', the largest sum in the LDM partition is at most <math>\frac{4}{3}-\frac{1}{3 (n-k-1)}</math> times the optimum,
*In all cases, the largest sum in the LDM partition is at most <math>\frac{4}{3}-\frac{1}{3 k}</math> times the optimum, and there are instances in which it is at least <math>\frac{4}{3}-\frac{1}{3 (k-1)}</math> times the optimum.
*For two-way partitioning, when inputs are uniformly-distributed random variables, the expected difference between largest and smallest sum is <math>n^{-\Theta(\log n)}</math>.
== Balanced two-way partitioning{{Anchor|balanced}} ==
Line 76:
#Run LDM on the set of differences.
BLDM has average properties similar to LDM. For two-way partitioning, when inputs are uniformly-distributed random variables, the expected difference between largest and smallest sum is <math>n^{-\Theta(\log n)}</math>.<ref name=":1" />
For multi-way partitioning, when ''c''=ceiling(''n''/''k'') and each of the ''k'' subsets must contain either ceiling(''n''/''k'') or floor(''n''/''k'') items, the approximation ratio of BLDM for the minimum largest sum is exactly 4/3 for ''c''=3, 19/12 for ''c''=4, 103/60 for ''c''=5, 643/360 for ''c''=6, and 4603/2520 for ''c''=7. The ratios were found by solving a [[Mixed integer linear programming|mixed integer linear program]]. In general (for any ''c''), the approximation ratio is at least <math>2-\sum_{j=0}^{c-1}\frac{j!}{c!}</math> and at most <math>2-\frac{1}{c-1}</math>. The MILP results for 3,4,5,6,7 correspond to the lower bound. When the parameter is the number of subsets (''k''), the approximation ratio is exactly <math>2-\frac{1}{k}</math>.<ref>{{Citation|last=Michiels|first=Wil|title=Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem|date=2003|url=https://link-springer-com.mgs.ariel.ac.il/chapter/10.1007/3-540-36494-3_51|work=Lecture Notes in Computer Science|pages=583–595|place=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|doi=10.1007/3-540-36494-3_51|access-date=2021-10-15|last2=Korst|first2=Jan|last3=Aarts|first3=Emile|last4=van Leeuwen|first4=Jan}}</ref>
Line 84:
== An exact algorithm ==
The '''complete Karmarkar–Karp algorithm (CKK)''' finds an optimal solution by constructing a tree of degree <math>k!</math>.
* In the case ''k''=2, each level corresponds to a pair of numbers, and the two branches correspond to taking their difference (i.e. putting them in different sets), or taking their sum (i.e. putting them in the same set).
* For general ''k'', each level corresponds to a pair of ''k''-tuples, and each of the <math>k!</math> branches corresponds to a different way of combining the subsets in these tuples.
For ''k''=2, CKK runs substantially faster than the [[Greedy number partitioning|Complete Greedy Algorithm (CGA)]] on random instances. This is due to two reasons: when an equal partition does not exist, CKK often allows more trimming than CGA; and when an equal partition does exist, CKK often finds it much faster and thus allows earlier termination. Korf reports that CKK can optimally partition 40 15-digit double-precision numbers in about 3 hours, while CGA requires about 9 hours. In practice, with ''k''=2, problems of arbitrary size can be solved by CKK if the numbers have at most 12 [[Significant figures|significant digits]]; with ''k''=3, at most 6 significant digits.<ref name=":0">{{Cite journal|last=Korf|first=Richard E.|date=1995-08-20|title=From approximate to optimal solutions: a case study of number partitioning|url=https://dl.acm.org/doi/abs/10.5555/1625855.1625890|journal=Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 1|series=IJCAI'95|___location=Montreal, Quebec, Canada|publisher=Morgan Kaufmann Publishers Inc.|pages=266–272|isbn=978-1-55860-363-9}}</ref>
Line 93:
CKK can also run as an [[anytime algorithm]]: 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).<ref>{{Cite journal|last=Korf|first=Richard E.|date=1998-12-01|title=A complete anytime algorithm for number partitioning|url=http://www.sciencedirect.com/science/article/pii/S0004370298000861|journal=Artificial Intelligence|language=en|volume=106|issue=2|pages=181–203|doi=10.1016/S0004-3702(98)00086-1|issn=0004-3702}}</ref>
Combining CKK with the balanced-LDM algorithm (BLDM) yields a complete [[anytime algorithm]] for solving the [[balanced partition problem]].<ref>{{
== Previous mentions ==
|