On the vertex characterization of single-shape partition polytopes

Yu-Chi Liu () and Jun-Jie Pan ()
Additional contact information
Yu-Chi Liu: Monash University
Jun-Jie Pan: Fu Jen Catholic University

Journal of Combinatorial Optimization, 2011, vol. 22, issue 4, No 7, 563-571

Abstract: 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.

Keywords: Sum-partition problem; Single-shape partition problem; Partition polytope; Separable partition; Polytope vertex (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9305-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:22:y:2011:i:4:d:10.1007_s10878-010-9305-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9305-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().