Publication: Semidefinite Relaxations of Ordering Pr...
Master data
Title: | Semidefinite Relaxations of Ordering Problems |
Subtitle: | |
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: |
Publication type: | Article in journal (Authorship) |
Publication date: | 01.08.2013 (Print) |
Published by: |
Mathematical Programming
Mathematical Programming
(
Springer Verlag GmbH;
)
to publication |
Title of the series: | - |
Volume number: | 140 |
Issue: | 1 |
First publication: | Yes |
Version: | - |
Page: | pp. 77 - 97 |
Versionen
Keine Version vorhanden |
Publication date: | |
ISBN (e-book): | - |
eISSN: | - |
DOI: | http://dx.doi.org/10.1007/s10107-012-0627-7 |
Homepage: | - |
Open access |
|
Publication date: | 01.08.2013 |
ISBN: | - |
ISSN: | - |
Homepage: | - |
Authors
P. Hungerländer
No Data available
*
|
F. Rendl
No Data available
*
|
Philipp Hungerländer (internal) |
Franz Rendl (internal) |
Assignment
Organisation | Address | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Categorisation
Subject areas | |
Research Cluster | No research Research Cluster selected |
Citation index |
Information about the citation index: Master Journal List
|
Peer reviewed |
|
Publication focus |
Classification raster of the assigned organisational units:
|
working groups | No working group selected |
Cooperations
No partner organisations selected
Research activities
All related research activities to this publication are shown here. With the link below, you can view them in the search view where you are also able to export them.
Show related search activities in search
Projects: |
|
Publications: | No related publications |
Events: | No related events |
Lectures: | No related lectures |
Articles of the publication
No related publications