On the vertex characterization of single‐shape partition polytopes

On the vertex characterization of single‐shape partition polytopes

0.00 Avg rating0 Votes
Article ID: iaor201111126
Volume: 22
Issue: 4
Start Page Number: 563
End Page Number: 571
Publication Date: Nov 2011
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: graphs
Abstract:

Given a partition of distinct d‐dimensional vectors into p parts, the partition sum of the partition is the sum of vectors in each part. The shape of the partition is a p‐tuple of the size of each part. A single‐shape partition polytope is the convex hull of partition sums of all partitions that have a prescribed shape. A partition is separable if the convex hull of its parts are pairwise disjoint. The separability of a partition is a necessary condition for the associated partition sum to be a vertex of the single‐shape partition polytope. It is also a sufficient condition for d=1 or p=2. However, the sufficiency fails to hold for d≥3 and p≥3. In this paper, we give some geometric sufficient conditions as well as some necessary conditions of vertices in general d and p. Thus, the open case for d=2 and p≥3 is resolved.

Reviews

Required fields are marked *. Your email address will not be published.