Optimization Online


Semidefinite Relaxations of Ordering Problems

Philipp Hungerländer (philipp.hungerlaender***at***uni-klu.ac.at)
Franz Rendl (franz.rendl***at***uni-klu.ac.at)

Abstract: 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.

Keywords: semidefinite programming, ordering problems, linear ordering, linear arrangement, crossing minimization, srflp, betweenness, quadratic ordering

Category 1: Combinatorial Optimization

Citation: Preprint, Alpen-Adria-Universität Klagenfurt, August 2010.

Download: [PDF]

Entry Submitted: 08/03/2010
Entry Accepted: 08/03/2010
Entry Last Modified: 01/19/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society