Name
Title | ||
|---|---|---|
Vertex characterization of partition polytopes of bipartitions and of planar point sets |
Abstract | ||
|---|---|---|
The partition problem concerns the partitioning of n given vectors in d-space into p parts, so as to maximize an objective function which is convex on the sum of vectors in each part. The problem has applications in diverse fields that include clustering, inventory, scheduling and statistical hypothesis testing. Since the objective function is convex, the partition problem can be reduced to the problem of maximizing the same objective over the partition polytope, defined to be the convex hull of all solutions. In this article we completely characterize the vertices of partition polytopes when either d=2 or p=2, and determine the maximum number of vertices of any partition polytope of n vectors when d=2 or p=2 up to a constant factor. Our characterization implies a bijection between vertices of the polytope of 0-separable partitions, and is best possible in the sense that there are examples in the literature showing the analogue fails already for p=d=3. Our enumerative results provide lower bounds on the time complexity needed to solve the partition problem when the objective function is presented by an oracle. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0166-218X(01)00326-2 | Discrete Applied Mathematics |
Keywords | Field | DocType |
constant factor,convex hull,vertex characterization,planar point set,p part,partition problem,partition problem concern,objective function,partition polytopes,n vector,0-separable partition,partition polytope,lower bound,time complexity,statistical hypothesis testing | Partition problem,Discrete mathematics,Combinatorics,Rank of a partition,Polytope,Convex polytope,Frequency partition of a graph,Graph partition,Vertex enumeration problem,Partition refinement,Mathematics | Journal |
Volume | Issue | ISSN |
124 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 0.79 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Aviran | 1 | 14 | 4.08 |
| Nissan Lev-Tov | 2 | 137 | 7.91 |
| Shmuel Onn | 3 | 420 | 54.77 |
| Uriel G. Rothblum | 4 | 595 | 125.62 |