Content deleted Content added
m Open access bot: url-access=subscription updated in citation with #oabot. |
|||
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 93:
== 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 ==
| |||