๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Determining adjacent vertices on assignment polytopes

โœ Scribed by Patrick G. McKeown

Publisher
John Wiley and Sons
Year
1976
Tongue
English
Weight
353 KB
Volume
23
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Abstract

To rank the solutions to the assignment problem using an extreme point method, it is necessary to be able to find all extreme points which are adjacent to a given extreme solution. Recent work has shown a procedure for determining adjacent vertices on transportation polytopes using a modification of the Chernikova Algorithm. We present here a procedure for assignment polytopes which is a simplification of the more general procedure for transportation polytopes and which also allows for implicit enumeration of adjacent vertices.

๐Ÿ“œ SIMILAR VOLUMES

On multi-index assignment polytopes
On multi-index assignment polytopes
โœ G. Appa; D. Magos; I. Mourtos ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 232 KB
Adjacency on the constrained assignment
Adjacency on the constrained assignment problem
โœ Abdo Y. Alfakih; Katta G. Murty ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 416 KB

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