Approximating Bin Packing within O(log OPT*loglog OPT) bins - todo314 @ ウィキ

Approximating Bin Packing within O(log OPT*loglog OPT) bins

• Thomas Rothvoss
• In FOCS 2013

• Bin Packing
  • s_1,…,s_n∈[0,1]
• 既存
  • OPT+O(log^2 OPT)
    • 30年位更新されなかった
  • OPT+O(log OPT*loglog OPT)にしたお！！！！
• Discrepancy Theoryとかいうのを使う

FOCS

2013-11-03 03:08:18 (Sun)