.png){kind=icon}
.png){kind=icon}
Return
Tighter bounds for the harmonic bin packing algorithm
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2024.01.051.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The harmonic algorithm, defined for online bin packing, partitions items into a fixed number M of classes of similar items, and packs each class independently and greedily in constant time for every packed item. The positive integer M is a parameter of the algorithm. This algorithm had a major role in the development of the online bin packing problem. Tight bounds on its asymptotic approximation ratio were known for M <= 7, and for values of M with specific properties. The parametric variant of this algorithm, where item sizes are bounded from above by a certain value, was studied as well. We find tight bounds for many additional cases that were known as open, including the case M = 8 for the classic problem.
Keywords:
Bin packing
Asymptotic approximation ratio
Bounded space algorithms
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W