Equality of complexity classes P and NP: Linear programming formulation of the quadratic assignment problem

Simple item page
dc.creatorDiaby, Moustapha
dc.date2006-09-02
dc.date2007-05-13
dc.date.accessioned2026-07-07T08:00:52Z
dc.date.available2026-07-07T08:00:52Z
dc.descriptionIn this paper, we present a polynomial-sized linear programming formulation of the Quadratic Assignment Problem (QAP). The proposed linear program is a network flow-based model. Hence, it provides for the solution of the QAP in polynomial time. Computational testing and results are discussed.
dc.description6 pages; Published in the 2006 IMECS Conference Proceedings (ISBN: 988 98671-3-3); Hofman's claimed "counter-example" is invalid: violates set of constraints 2.10
dc.identifierhttps://arxiv.org/abs/cs/0609004
dc.identifierhttp://arxiv.org/abs/cs/0609004
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/128781
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectF.2.2
dc.titleEquality of complexity classes P and NP: Linear programming formulation of the quadratic assignment problem
dc.typetext

Files

Collections

arXiv