We consider the following version of online bin packing. Arriving items of rational sizes in (0, 1] belong to a constant number of types denoted by $$1,2,\ldots ,k$$ 1 , 2 , … , k , and there are unbounded numbers of available bins of these types. The cost of a bin depends on its type, and the sequence of costs is monotonically increasing. Every item of type i can be packed into a bin of type whose index is at least i , and no bin may have a total size of items that is larger than 1. Items are presented one by one to be packed into suitable bins, where the information regarding bin types is known in advance. The cost of the algorithm is the total cost of used bins, and the goal is to minimize the cost. We show tight bounds on the absolute competitive ratio for the case of three types ( $$k=3$$ k = 3 ), and tight bounds for the overall bound with an arbitrary number of types k , where those bounds are 2 and 4 for $$k=3$$ k = 3 and for arbitrary k , respectively.
Epstein, Leah. Bin packing with hierarchical item types. // Annals of Operations Research. – 2026. – DOI: 10.1007/s10479-026-07475-5. – URL: http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10479-026-07475-5
Epstein & Leah (2026). Bin packing with hierarchical item types. Annals of Operations Research. https://doi.org/10.1007/s10479-026-07475-5
Epstein and Leah. “Bin packing with hierarchical item types.” Annals of Operations Research, 2026. doi:10.1007/s10479-026-07475-5.
@article{Epstein2026,
title = {Bin packing with hierarchical item types},
author = {Epstein and Leah},
journal = {Annals of Operations Research},
year = {2026},
doi = {10.1007/s10479-026-07475-5},
url = {http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10479-026-07475-5}
}
In this paper, we consider cost-sharing problems defined on rooted trees. We refer to these problems as cost-tree problems and to the induced transferable utility cooperative games as irrigation games. We introduce a formal notion of...
In this paper, we focus on nonlinear programming problems with cardinality constraints that restrict the number of nonzero components of the decision vector. We start with a straightforward mixed-integer programming reformulation....
Portfolio selection is a critical issue in financial management under uncertainty. In this paper, we propose a complex approach for portfolio selection with quantile return approximation. In particular, we propose a practical workflow...
The transcendental logarithmic (translog) production function is recognised as a flexible functional form for modelling production processes. It accommodates varying elasticities of input substitution and diverse types of...
This study investigates mothership-drone route determination using two optimization approaches: a Mixed Integer Linear Programming (MILP) model based on a discrete hexagonal grid, and a Mixed Integer Nonlinear Programming (MINLP) model...