Content deleted Content added
Citation bot (talk | contribs) Alter: journal, pages. Add: authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform |
→Two-way partitioning: Fixed example that was wrong and led to confusion s when trying to understand the backtracking step of the algorithm. Tags: Mobile edit Mobile web edit |
||
Line 16:
For example, if S = {8,7,6,5,4}, then the resulting difference-sets are 6,5,4,1, then 4,1,1, then 3,1 then 2.
Step 3 constructs the subsets in the partition by backtracking. The last step corresponds to {2},{}. Then 2 is replaced by 3 in one set and 1 in the other set: {3},{1}, then {4},{1,1}, then {4,
The runtime complexity of this algorithm is dominated by the step 1 (sorting), which takes O(''n'' log ''n'').
Line 25:
* 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|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>
=== Multi-way partitioning ===
| |||