The minimum linear arrangement problem on proper interval graphs
  We present a linear time algorithm for the minimum linear arrangement problem on proper interval graphs. The obtained ordering is a 4-approximation for general interval graphs 
Ilya Safro