COS JIW - Fall 2003	Lorenzo Orecchia 
TITLE: Mathematical Programming Relaxations of the Linear Ordering Problem

PROJECT OUTLINE
The linear ordering problem is known to be NP-hard. In recent years research has focused on finding polynomial approximations for this problem to improve the trivial 2-approximation. As the linear ordering problem is easily converted into an integer program, linear programming relaxations have been a natural choice to in the quest for approximate solutions. However, these relaxations have been proved not to consistently improve the approximation ratio of the trivial approximation. 
In this project, we will consider the working of semidefinite programming relaxations of the same problem, in the attempt to verify whether the higher generality of SDP gifts us with any more power over LP.
To this end the first step of the project will be to consider the results of the SDP relaxations when applied to the set of extremal graphs which are known "bad cases" for the LP relaxations.
Depending on the result of this and on the available time, the project might get involved in the search of a rounding algorithm or of more constraints to place on the SDP relaxations.


10 October 2003