MINIMUM CUT LINEAR ARRANGEMENT

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

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

• MEASURE: Maximum number of cut edges in any integer point, i.e.

  
  

  $$\max_{i\in [1..\vert V\vert}\vert\{\{u,v\}\in E: f(u)\le i <f(v)\}\vert.$$
  
  

  
  

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

• Comment: Admits a PTAS if $\vert E\vert =\Theta(\vert V\vert^2)$ [36].

• Garey and Johnson: GT44