Content deleted Content added
Erel Segal (talk | contribs) |
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.
=== Balanced two-way partitioning ===
Benjamin Yakir<ref name=":1" /> extended LDM to the ''balanced'' number partitioning problem, in which all subsets must have the same cardinality (up to 1). His BLDM algorithm for ''k''=2 works as follows (where the items are ordered from largest to smallest);
* 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.
== Implementation ==
| |||