The Minimum Linear Arrangement Problem



The MINLA problem is a classified NP-hard optimization problem. It can be defined as:

-Undirected and unweighted graph G = (V,E).

-A one to one function .




In the MINLA problem, the goal is to arrange the vertices of a given graph on an integer line ( -label assignment) , so as to minimize the following cost formuma C:



Problem Instances

In order to define an instance of this problem we need to provide all the information about the Graph. This means: his Vertex Set and the associated Edge Set between pairs of vertexs. The edges are unweighted.


Related Bibliography and Papers

Computers and Intractability: A Guide to the Theory of Np-Completeness
by Michael R. Garey, David S. Johnson
How to Solve It: Modern Heuristics
by Zbigniew Michalewicz, David B. Fogel

Aproximation Heuristics and Benchmarkings for the MinLA Problem

A compendium of NP optimization problems

Last Updated: 5/06/03                                                                                                                  For any question or suggestion, click here to contact with us.