Minimal on-line labelling

Richard S. Bird, and Stefan Sadnicki
Information Processing Letters
Volume 101, Issue 1 , 16 January 2007, Pages 41-45
http://dx.doi.org/10.1016/j.ipl.2006.07.011

N人が次々と順番にやって来るので，1列に並んだN個の席に順に座らせることを考える．
ただし，N個の席にはN人を背の順 (などのある線形順序) に従って座らせなければならないが，次にどれくらいの背の高さの人が来るのか前もって分かっていない．
うまくいかない場合にはその時点までに座った人に動いてもらう必要がある．
そのような再配置の回数を最小にするようなアルゴリズムはどんなものか，この論文は考察している．
これは順序を保ったままリストを更新する問題の特殊な場合で，さらにその更新が挿入だけのsemi-dynamicバージョンである．
知られているアルゴリズム (Zhang 1993, Andersson and Lai 1990) では再配置回数がO(N log^3 N)になるが，少しややこしいらしい．
この論文ではそのアルゴリズムを解説して，単純化した解析を紹介している．
下界もΩ(N log^3 N)となることが予想されているが，まだ分かっていないらしい．