The use of special graphs for obtaining lower bounds in the geometric quadratic assignment problem
Volume 8, Issue 3 (1997), pp. 377–400
Pub. online: 1 January 1997
Type: Research Article
Published
1 January 1997
1 January 1997
Abstract
In this paper we define a class of edge-weighted graphs having nonnegatively valued bisections. We show experimentally that complete such graphs with more than three vertices and also some special graphs with only positive edges can be applied to improve the existing lower bounds for a version of the quadratic assignment problem, namely with a matrix composed of rectilinear distances between points in the Euclidean space.