Average-case analysis of the modified harmonic algorithm

DOI10.1007/BF01553906zbMath0684.68059OpenAlexW2067058623MaRDI QIDQ1825655

Kazuhiro Tsuga, Prakash V. Ramanan

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01553906

zbMATH Keywords

approximation algorithmon-line algorithmworst-case performancebin packingaverage-case performance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Randomized algorithms for the on-line minimum matching problem on euclidean space ⋮ Packings in two dimensions: Asymptotic average-case analysis of algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Probabilistic analysis for simple one- and two-dimensional bin packing algorithms
• A simple on-line bin-packing algorithm
• A stochastic model of bin-packing
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• On-line bin packing in linear time
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations