Content deleted Content added
m Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published) |
Citation bot (talk | contribs) Alter: url. URLs might have been anonymized. Add: eprint, isbn, volume, series, s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
||
Line 25:
* 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}}</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 53:
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://
# Order the numbers from large to small.
Line 78:
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|
== 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|
== An exact algorithm ==
Line 93:
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.|date=1998-12-01|title=A complete anytime algorithm for number partitioning|url=http://www.sciencedirect.com/science/article/pii/S0004370298000861|journal=Artificial Intelligence|language=en|volume=106|issue=2|pages=181–203|doi=10.1016/S0004-3702(98)00086-1|issn=0004-3702}}</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|
== Previous mentions ==
| |||