A note on the Kenyon‐Remila strip-packing algorithm

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 $\mathit{OPT}+O(\sqrt{\mathit{OPT}\log \mathit{OPT}})$ where OPT is the optimal value.