Markov chains, computer proofs, and average-case analysis of best fit bin packing

DOI10.1145/167088.167203zbMath1310.68271OpenAlexW2055119378MaRDI QIDQ5248510

David S. Johnson, Richard R. Weber, Edward G. jun. Coffman, Peter W. Shor

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167203

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Online algorithms; streaming algorithms (68W27)

Related Items (7)

Linear waste of best fit bin packing on skewed distributions ⋮ Computer-assisted proof of performance ratios for the differencing method ⋮ Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison ⋮ Average-case analyses of first fit and random fit bin packing ⋮ Average case analysis of bounded space bin packing algorithms ⋮ Matching random colored points with rectangles ⋮ Bounded-space online bin cover

This page was built for publication: Markov chains, computer proofs, and average-case analysis of best fit bin packing