Largest differencing method: Difference between revisions

Revision as of 18:22, 14 October 2021

Revision as of 18:40, 14 October 2021

Line 50:

*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 ===

BenjaminSeveral Yakir<refvariants name=":1"of />LDM extendedwere LDMdeveloped tofor 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);

A variant of LDM, called ''paired'PDM differencing(Paired methodDifferencing (PDMMethod)'',' works as follows.<ref>{{Cite journal|last=Lueker|first=George S|date=1987-12-01|title=A note on the average-case behavior of a simple differencing method for partitioning|url=https://www.sciencedirect.com/science/article/pii/0167637787900447|journal=Operations Research Letters|language=en|volume=6|issue=6|pages=285–287|doi=10.1016/0167-6377(87)90044-7|issn=0167-6377}}</ref>

* 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>.

=== Paired differencing method ===

A variant of LDM, called ''paired differencing method (PDM)'', works as follows.<ref>{{Cite journal|last=Lueker|first=George S|date=1987-12-01|title=A note on the average-case behavior of a simple differencing method for partitioning|url=https://www.sciencedirect.com/science/article/pii/0167637787900447|journal=Operations Research Letters|language=en|volume=6|issue=6|pages=285–287|doi=10.1016/0167-6377(87)90044-7|issn=0167-6377}}</ref>

# Order the numbers from large to small.

Line 64 ⟶ 59:

#If two or more numbers remain, return to step 1.

# Using [[backtracking]], compute the partition.

PDM has average properties worse than LDM. For two-way partitioning, when inputs are uniformly-distributed random variables, the expected difference between largest and smallest sum is <math>\Theta(1/n)</math>.

'''RLDM (Restricted Largest Differencing Method)''' works as follows.<ref name=":5">{{Cite journal|last=Tsai|first=Li-Hui|date=1992-02-01|title=Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling|url=https://epubs.siam.org/doi/abs/10.1137/0221007|journal=SIAM Journal on Computing|volume=21|issue=1|pages=59–64|doi=10.1137/0221007|issn=0097-5397}}</ref>

#Order the numbers from large to small.

* #Replace numbers #1 and #2 by their difference; replace numbers #3 and #4 by their difference; etc.

*#Sort Oncethe therelist areof ''n''/2 differences, runfrom LDMlarge to small.

#Assign each pair in turn to different sets: the largest in the pair to the set with the smallest sum, and the smallest in the pair to the set with the largest sum.

For two-way partitioning, when inputs are uniformly-distributed random variables, the expected difference between largest and smallest sum is <math>O(\log{n}/n^2)</math>.

'''BLDM (Balanced Largest Differencing Method)''' works as follows.<ref name=":1" />

#Order the numbers from large to small.

#Replace numbers #1 and #2 by their difference; #3 and #4 by their difference; etc.

#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>.

== Implementation ==