Copositive and semidefinite relaxations of the quadratic assignment problemPovh, Janez, 1973- ; Rendl, FranzSemidefinite 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.Source: Discrete optimization. - ISSN 1572-5286 (Vol. 6, iss. 3, 2009, str. 231-241)Type of material - article, component partPublish date - 2009Language - englishCOBISS.SI-ID - 15143001
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Select the library membership card:
DRS, in which the journal is indexed
Select pickup location:
Material pickup by post
Subject headings in COBISS General List of Subject Headings
Please wait a moment.