Improved bounds for the unsplittable flow problem

Petr Kolman and Christian Scheideler
Journal of Algorithms
Volume 61, Issue 1 , September 2006, Pages 20-44
http://dx.doi.org/10.1016/j.jalgor.2004.07.006

SODA2004論文のジャーナル版．ようやく出た．
Unsplittable flow problem (多品種流問題の01バージョン) に対する近似アルゴリズムの話．
特に，ある種の貪欲アルゴリズムを考えている．
この論文は私がチューリッヒに行って3ヶ月ぐらいしたときに始めたプロジェクトで渡された論文であり，なかなか内容が理解できなかったけど，そこから何とかして結果を出したという思い出がある．