Computer Science NASC Seminar

Semidefinite Programming Applied to Ordering Problems

Franz Rendl, University of Klagenfurt

February 25, 2011 10:00AM
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 10012-1110

Spring 2011 NASC Seminars Calendar


Ordering problems assign weights to each ordering and ask to
find an ordering of maximum weight.
We consider problems where the cost function is either linear
or quadratic. In the first case, there is a given profit if
the element $u$ is before $v$ in the ordering.
In the second case, the profit depends on whether $u$
is before $v$ and $r$ is before $s$.

The linear ordering problem is well studied, with exact solution
methods based on polyhedral relaxations. The quadratic ordering
problem does not seem to have attracted similar attention.
We present a systematic investigation of semidefinite optimization
based relaxations for the quadratic ordering problem, extending
and improving existing approaches.
We show the efficiency of our relaxations by providing computational
experience on a variety of problem classes.

(This is joint work with my doctoral student Philipp Hungerlaender.)

top | contact webmaster