Jünger, Michael and Kaibel, Volker
(1996).
A Basic Study of the QAP-Polytope.
["eprint_fieldopt_monograph_type_preprint" not defined].
|
PDF
zpr96-215.pdf Download (308kB) | Preview |
Abstract
We investigate a polytope (the 'QAP-Polytope') beyond a 'natural' integer programming formulation of the Quadratic Assignment Problem (QAP) that has been used successfully in order to compute good lower bounds for the QAP in the very recent years. We present basic structural properties of the QAP-Polytope, partially independently also obtained by Rijal (1995). The main original contribution of this work is the representation of the QAP-Polytope in a space different from the one in which it is defined naturally. This representation provides us with a much simpler way to derive the dimension of the QAP-Polytope, as well as to investigate the facial structure of it. Furthermore, it leads to some interesting observations concerning the combinatorial structure of the QAP-Polytope.
| Item Type: | Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined]) | ||||||||||||
| Creators: |
|
||||||||||||
| URN: | urn:nbn:de:hbz:38-547045 | ||||||||||||
| Date: | 1996 | ||||||||||||
| Language: | English | ||||||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||||||
| Subjects: | Data processing Computer science | ||||||||||||
| Refereed: | No | ||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54704 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |