Probabilistic analysis of a heuristic for the dual bin packing problem

DOI10.1016/0020-0190(89)90088-4zbMath0682.68045OpenAlexW1987979082MaRDI QIDQ1824388

Rakesh V. Vohra, Dean P. Foster

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90088-4

zbMATH Keywords

probabilistic analysisbin packingfirst fit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05)

Related Items

An exact algorithm for the dual bin packing problem, Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations, Upper bounds and algorithms for the maximum cardinality bin packing problem., Lower bounds and algorithms for the minimum cardinality bin covering problem, Dual bin packing with items of random sizes

Cites Work

• Probabilistic bounds for dual bin-packing
• Bin packing: Maximizing the number of pieces packed
• Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation
• Optimal selection of stochastic intervals under a sum constraint
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations