The price of clustering for bin packing with cluster cost at least 3 is bounded between 1.93558 and 1.93667, and the competitive ratio for online bin packing with delays is improved to below 3.1551.
A new lower bound for classic online bin packing
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403.
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On bin packing with clustering and bin packing with delays
The price of clustering for bin packing with cluster cost at least 3 is bounded between 1.93558 and 1.93667, and the competitive ratio for online bin packing with delays is improved to below 3.1551.