A note on the Kenyon¨CRemila strip-packing algorithm

详细信息    查看全文

• 作者：Maxim Sviridenko ;   ; ^{sviri@us.ibm.com}
• 关键词：Bin packing ; Approximation algorithms ; Strip packing
• 刊名：Information Processing Letters
• 出版年：2012
• 出版时间：15 January 2012
• 年：2012
• 卷：112
• 期：1-2
• 页码：10-12
• 全文大小：119 K

文摘

We show that a modification of the Kenyon¨CRemila 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 where mlns="""">OPT is the optimal value.