Adjacency on the constrained assignment problem

✍ Scribed by Abdo Y. Alfakih; Katta G. Murty

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 416 KB
• Volume: 87
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00063-8

✦ Synopsis

Let Qc,, be the integer hull of the intersection of the assignment polytope with a given hyperplane H = {X = (xii) E Wx" : c:=, cJ=, ct,xij = r}. W e 5 .h ow that the problem of checking whether two given extreme points of Qc,r are nonadjacent c = (cl,) is a O-l matrix, and that it is NP-Complete if c Elsevier Science B.V. All rights reserved.