MINIMUM LINEAR ARRANGEMENT

• INSTANCE: Graph $G=\left(V,E\right)$.

• SOLUTION: A one-to-one function $f:V\rightarrow[1..\vert V\vert$].

• MEASURE: The total length of the edges in the linear arrangement, i.e. $\sum_{\{u,b\}\in E}\vert f(u)-f(v)\vert$.

  
  

• Good News: Approximable within $O(\log \vert V\vert)$ [416].

• Comment: Admits a PTAS if $\vert E\vert =\Theta(\vert V\vert^2)$. Variation in which the n points are on the d-dimensional grid instead of in a line and the rectilinear metric is used also admits a PTAS if $\vert E\vert =\Theta(\vert V\vert^2)$ [36].

• Garey and Johnson: GT42