Permutation Polytopes and OPtimal Partitions
F. K. Hwang
|Keywords:||多面體;排列多面體;最優分割;排序性;polytope;permutation polytope;optimal partition;sortability|
When we try to find a partition that maximizes an objective function over a given family of partitions, a brute force approach is hopeless since the number of all partitions in the family is usually exponentially many. Hence we need to identify a polynomial-size class of partitions and prove the existence of an optimal partition in such a class. Many such classes have been proposed and studied for partitions in R and most of them enumerated. We will provide some simple formulas and direct arguments for the enumeration of several classes. One of the most important class is the class of consecutive partitions. We call a partition of consecutive if each of its parts consists of consecutive integers. Barnes, Hoffman and Rothblum first studied the optimal partition problem through the partition polytope, the convex hull of all partitions in the family. They proved that the vertices of the partition polytope are associated with consecutive partitions; so linear or convex programming can be used when the objective function is linear or convex. We will extend the notion of partition polytope to permutation polytope corresponding to a real-valued function. While the properties of partition classes have been very well developed in R, we extend the study to partition classes in higher dimensions. We enumerate these classes and also derive some combinatorial properties like consistency and sortability which have been well studied in R.
|Appears in Collections:||Thesis|