Generating lower bounds for the linear arrangement problem

The linear arrangement problem is a fundamental problem that arises in many practical applications such as VLSI circuit layout. In this paper, the authors present two methods to evaluate the lower bound of the linear arrangement problem in graphs. The first method uses a linear programming formulation which is based on the rank constraints. The second method uses the information provided by a minimum cuts algorithm to generate these lower bounds. Computational results and comparisons of both techniques against a Gomory-Hu tree based approach indicate that the generated lower bounds are very tight.