排列多面體與最優分割

Abstract

當我們要在一分割族中找出一個使目標函數達到最優(最大或最小)的分割，因為在這個分割族中分割的數目通常是指數型的，利用暴力法是沒有用的。因此，我們必須找到分割數目為多項式型的分割類，並且證明在此分割類中有最優分割存在。在實數中，已經有很多如此分割類被提出並討論，我們將對其中一些分割類的計數提出簡單公式與直接的證明。 連續分割類是最重要的分割類之一，Barns、Hoffman與Rothblum首先利用分割多面體研究最優分割問題，他們證明分割多面體的頂點與連續分割對應，因此當目標函數是線性(或凸性)時，可以利用線性(或凸性)規劃解決最優分割問題。我們將分割多面體的結果擴展到對應於實數值函數的排列多面體。 在實數中，分割類的性質已經有很好的發展，我們將擴展到高維度，討論一些值得研究的分割類。我們計算這些分割類的數目，也像實數中討論如一致性、排序性等組合性質。

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.