Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
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, and 643/360 for ''c''=6. In general (for ''c'' at least 7), the approximation ratio is between <math>2-\frac{2}{c}</math> and <math>2-\frac{1}{c-1}</math>. 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>
== Implementation ==
| |||