Probabilistic analysis of algorithms for dual bin packing problems

DOI10.1016/0196-6774(91)90001-FzbMath0734.68050OpenAlexW2172277188WikidataQ89139025 ScholiaQ89139025MaRDI QIDQ3361889

Gábor Galambos, Alexander H. G. Rinnooy Kan, J. B. G. Frenk, János A. Csirik

Publication date: 1991

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(91)90001-f

zbMATH Keywords

bin packing problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Online bin covering: expectations vs. guarantees, An exact algorithm for the dual bin packing problem, Integer linear programming models for the skiving stock problem, Online algorithms for a dual version of bin packing, The skiving stock problem and its relation to hypergraph matchings, Approximation and online algorithms for multidimensional bin packing: a survey, Probabilistic analysis of a bin covering algorithm, Large proper gaps in bin packing and dual bin packing problems, Selfish bin covering, Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case, The proper relaxation and the proper gap of the skiving stock problem, Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory, Integer rounding and modified integer rounding for the skiving stock problem, An upper bound of \(\Delta(E) < 3 \slash 2\) for skiving stock instances of the divisible case, Packing resizable items with application to video delivery over wireless networks, Bounded-space online bin cover, Optimal on-line algorithms for variable-sized bin covering, Online variable sized covering, Online Bin Covering: Expectations vs. Guarantees