Tighter bounds for the harmonic bin packing algorithm

Leah Epstein

European Journal of Operational Research, 2024, vol. 316, issue 1, 72-84

Abstract: 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 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724000912
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:316:y:2024:i:1:p:72-84

DOI: 10.1016/j.ejor.2024.01.051

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().