The polytope of block diagonal matrices and complete bipartite partitionings
✍ Scribed by Crama, Yves; Oosten, Maarten
- Publisher
- John Wiley and Sons
- Year
- 1997
- Tongue
- English
- Weight
- 259 KB
- Volume
- 30
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Motivated by a fundamental clustering problem arising in several areas (production management, marketing, numerical analysis, etc.), we investigate the facial structure of the polytope whose extreme points are all 0-1 block diagonal matrices. For this polytope, general properties of facet-defining inequalities are investigated and specific families of facets are identified. Various techniques for lifting or combining facet-defining inequalities into new ones are also presented. Throughout the paper, a block diagonal matrix is regarded as the adjacency matrix of a disjoint union of complete bipartite graphs. The presentation and the derivation of the results heavily rely on this graph-theoretic interpretation.