An improved approximation ratio for the minimum linear arrangement problem

Uriel Feige and James R. Lee
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 26-29
http://dx.doi.org/10.1016/j.ipl.2006.07.009

グラフの最小linear arrangement問題に対する近似アルゴリズム。
Arora, Rao and Vazirani (2004) による有限距離空間の埋め込み技法とRao and Richa (2004) の近似アルゴリズムを組み合わせて、O(\sqrt{log n}loglog n)近似アルゴリズムを設計している。
Rao and Richa (2004) のアルゴリズム自体はEven, Naor, Rao and Schieber (2000) による緩和を用いていて、この緩和自体がなかなか面白い。
同じ近似比の同様なアルゴリズムがCharikar, Hajiaghayi, Karloff and Rao (SODA 2006) でも得られている。