| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Copositive and semidefinite relaxations of the quadratic assignment problem
Authors:ID Povh, Janez (Author)
ID Rendl, Franz (Author)
Files:URL http://dx.doi.org/10.1016/j.disopt.2009.01.002
Work type:Not categorized (r6)
Typology:1.01 - Original Scientific Article
Organization:FL - Faculty of Logistic
Abstract:Semidefinite relaxations of the quadratic assignment problem (QAP) have recently turned out to provide good approximations to the optimal value of QAP. We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it is hard to optimize over this cone, we also look at tractable approximations and compare with several relaxations from the literature. We show that several of the well-studied models are in fact equivalent. It is still a challenging task to solve the strongest of these models to reasonable accuracy on instances of moderate size.
Keywords:matematično programiranje, problem kvadratičnega prirejanja, kopozitivno programiranje, semidefinitna poenostavitev, quadratic assignment problem, copositive programming, semidefinite relaxations, lift-and-project relaxations
Year of publishing:2009
Number of pages:str. 231-241
Numbering:Vol. 6, iss. 3
PID:20.500.12556/DKUM-51786 New window
ISSN on article:1572-5286
COBISS.SI-ID:15143001 New window
Publication date in DKUM:10.07.2015
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
AddThis uses cookies that require your consent. Edit consent...

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Discrete optimization
COBISS.SI-ID:513620761 New window


Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
There are no comments!

Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica