橋桁と調和数

たけしのコマネチ大学数学科で調和数の問題をやっていた (橋げたの話) 筈.
もしかすると最適解と言っているかも知れないが, それは最適解ではないということが示されていた. 悲しいかな論文の題名を忘れてしまったので検索出来ない. ICALP 2006だと思ったんだけどなぁ.

SODA 2006だった. Mike Paterson and Uri Zwick "Overhang"だ.

• Mike Peterson
• Uri Zwick
  • Overhang (ppsファイル)

n個のブロックで, 掛けられる長さをD(n)とする.
彼らの方針だと, が言えるので, n=1兆のとき, 5723くらいははみ出せる. 調和数でやると, もっと低く14くらい.
発表資料が良く出来ている.