Largest differencing method: Difference between revisions

Revision as of 08:47, 9 March 2025

Latest revision as of 09:58, 31 July 2025

(One intermediate revision by one other user not shown)

Line 37:

* 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> .<ref name=":1" />

* 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|s2cid=30065792|issn=1436-4646|url-access=subscription}}</ref> This is tight when there are 5 or more items.'''<ref name=":2" />'''

*On random instances, this approximate algorithm performs much better than [[greedy number partitioning]]. However, it is still bad for instances where the numbers are exponential in the size of the set.<ref name="hayes">{{citation|last=Hayes|first=Brian|title=The Easiest Hard Problem|date=March–April 2002|magazine=[[American Scientist]]|volume=90|issue=2|pages=113–117|publisher=Sigma Xi, The Scientific Research Society|jstor=27857621|author-link=Brian Hayes (scientist)}}</ref>

Line 65:

Several variants of LDM were developed for the [[balanced number partitioning]] problem, in which all subsets must have the same cardinality (up to 1).

'''PDM (Paired Differencing Method)''' 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://dx.doi.org/10.1016/0167-6377%2887%2990044-7|journal=Operations Research Letters|language=en|volume=6|issue=6|pages=285–287|doi=10.1016/0167-6377(87)90044-7|issn=0167-6377|url-access=subscription}}</ref>

# Order the numbers from large to small.

Line 73:

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|url-access=subscription}}</ref>

#Order the numbers from large to small.

Line 90:

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|last1=Michiels|first1=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|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|series=Lecture Notes in Computer Science|volume=2607|isbn=978-3-540-00623-7}}{{Dead link|date=July 2025 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>

== Min-max subsequence problem ==

In the ''min-max subsequence problem'', the input is a multiset of ''n'' numbers and an integer parameter ''k'', and the goal is to order the numbers such that the largest sum of each block of adjacent ''k'' numbers is as small as possible. The problem occurs in the design of video servers.<ref>Wil Michiels (2004). "Performance Ratios for Differencing Methods". Technische Universiteit Eindhoven, 2004. https://www.elibrary.ru/item.asp?id=8860464</ref> This problem can be solved in polytime for ''k''=2, but it is strongly NP-hard for ''k≥''3. A variance of the differencing method can applied to this problem.<ref>{{Cite journal|last1=Michiels|first1=Wil|last2=Korst|first2=Jan|date=2001|title=Min–max subsequence problems in multi-zone disk recording|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/jos.80|journal=Journal of Scheduling|language=en|volume=4|issue=5|pages=271–283|doi=10.1002/jos.80|issn=1099-1425|url-access=subscription}}</ref>

== An exact algorithm ==