Content deleted Content added
Added short description Tags: Mobile edit Mobile app edit Android app edit |
Rescuing 0 sources and tagging 1 as dead.) #IABot (v2.0.9.5 |
||
| (2 intermediate revisions by 2 users 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 ==
Line 101:
* For general ''k'', each level corresponds to a pair of ''k''-tuples, and each of the <math>k!</math> branches corresponds to a different way of combining the subsets in these tuples.
For ''k''=2, CKK runs substantially faster than the [[Greedy number partitioning|Complete Greedy Algorithm (CGA)]] on random instances. This is due to two reasons: when an equal partition does not exist, CKK often allows more trimming than CGA; and when an equal partition does exist, CKK often finds it much faster and thus allows earlier termination. [[Richard E. Korf]] reports that CKK can optimally partition 40 15-digit double-precision numbers in about 3 hours, while CGA requires about 9 hours. In practice, with ''k''=2, problems of arbitrary size can be solved by CKK if the numbers have at most 12 [[Significant figures|significant digits]]; with ''k''=3, at most 6 significant digits.<ref name=":0">{{Cite journal|last=Korf|first=Richard E.|author-link=Richard E. Korf|date=1995-08-20|title=From approximate to optimal solutions: a case study of number partitioning|url=https://dl.acm.org/doi/abs/10.5555/1625855.1625890|journal=Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 1|series=IJCAI'95|___location=Montreal, Quebec, Canada|publisher=Morgan Kaufmann Publishers Inc.|pages=266–272|isbn=978-1-55860-363-9}}</ref>
CKK can also run as an [[anytime algorithm]]: it finds the KK solution first, and then finds progressively better solutions as time allows (possibly requiring exponential time to reach optimality, for the worst instances).<ref>{{Cite journal|last=Korf|first=Richard E.|author-link=Richard E. Korf|date=1998-12-01|title=A complete anytime algorithm for number partitioning|journal=Artificial Intelligence|language=en|volume=106|issue=2|pages=181–203|doi=10.1016/S0004-3702(98)00086-1|issn=0004-3702|doi-access=free}}</ref>
Combining CKK with the balanced-LDM algorithm (BLDM) yields a complete [[anytime algorithm]] for solving the [[balanced partition problem]].<ref>{{cite arXiv|last=Mertens|first=Stephan|date=1999-03-11|title=A complete anytime algorithm for balanced number partitioning|eprint=cs/9903011}}</ref>
| |||