Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 79:
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, and 643/360 for ''c''=6. In general (for ''c'' at least 7), the approximation ratio is between <math>2-\frac{2}{c}</math> and <math>2-\frac{1}{c-1}</math>. When the parameter is the number of subsets (''k''), the approximation ratio is exactly <math>2-\frac{1}{k}</math>.<ref>{{Citation|last=Michiels|first=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|work=Lecture Notes in Computer Science|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}}</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|last=Michiels|first=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}}</ref>
== Implementation ==
| |||