Content deleted Content added
m Open access bot: url-access=subscription updated in citation with #oabot. |
Rescuing 0 sources and tagging 1 as dead.) #IABot (v2.0.9.5 |
||
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 ==
| |||