| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 1 / 1
First pagePrevious page1Next pageLast page
1.
Copositive and semidefinite relaxations of the quadratic assignment problem
Janez Povh, Franz Rendl, 2009, original scientific article

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
Published: 10.07.2015; Views: 499; Downloads: 63
URL Link to full text

Search done in 0.01 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica