| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Copositive and semidefinite relaxations of the quadratic assignment problem
Authors:Povh, Janez (Author)
Rendl, Franz (Author)
Files:URL http://dx.doi.org/10.1016/j.disopt.2009.01.002
 
Language:English
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
UDC:519.85
ISSN on article:1572-5286
COBISS_ID:15143001 Link is opened in a new window
NUK URN:URN:SI:UM:DK:FCHQ0ZVW
Views:504
Downloads:63
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:Misc.
:
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:AddThis
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
Publisher:Elsevier
ISSN:1572-5286
COBISS.SI-ID:513620761 New window

Comments

Leave comment

You have to log in to leave a comment.

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

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