Content deleted Content added
→Two-way partitioning: Fixed example that was wrong and led to confusion s when trying to understand the backtracking step of the algorithm. Tags: Mobile edit Mobile web edit |
Erel Segal (talk | contribs) |
||
Line 47:
*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>. <ref name=":1" />
=== Balanced two-way partitioning ===
Line 53 ⟶ 54:
* Replace numbers #1 and #2 by their difference; replace numbers #3 and #4 by their difference; etc.
* Once there are ''n''/2 differences, run LDM.
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>.
== Implementation ==
| |||