SIGACT News Online Algorithms Column 20: The Power of Harmony

摘要

I would like to begin this column by thanking Marek Chrobak, Lance Fortnow and Brendan Mumey for giving me this opportunity for continuing the online algorithms column started by Marek in 2003. I will begin by discussing a problem close to my heart, namely online bin packing. For the standard version of this problem, there has been very little progress in the last 10 years. I hope to bring some new attention to this important problem and hopefully convince some of you to give this some thought. I will also discuss some (but by no means all) recent results in strip packing and two-dimensional bin packing.