David S. Kung
DAC 1998
Paper
A note on the Kenyon-Remila strip-packing algorithm
Abstract
We show that a modification of the Kenyon-Remila algorithm for the strip-packing problem yields an improved bound on the value of the approximate solution. As a corollary we derive that there exists a polynomial-time algorithm that always finds a solution of value OPT+O(OPTlogOPT) where OPT is the optimal value. © 2011 Elsevier B.V. All rights reserved.
Related
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
Conference paper
A quantitative analysis of OS noise
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering