Name
Abstract | ||
|---|---|---|
The computational complexity of the partition problem , which concerns the partitioning of a set of n 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, is determined by the number of vertices of the corresponding p-partition polytope defined to be the convex hull in d p )-space of all solutions.In this article, introducing and using the class of Momentopes , we establish the lower bound p , d ( n )= Ω( n ( d 1)/2 M p ) on the maximum number of vertices of any p -partition polytope of a set of n points in d -space, which is quite compatible with the recent upper bound p , d ( n )= O ( n d ( p 1) 1, implying the same bound on the complexity of the partition problem. We also discuss related problems on the realizability of Davenport--Schinzel sequences and describe some further properties of Momentopes. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/s00454-001-0069-0 | Discrete & Computational Geometry |
Keywords | Field | DocType |
1. partition polytopes and partition problems,computational complexity,lower bound,convex hull,objective function | Partition problem,Discrete mathematics,Combinatorics,Vertex (geometry),Upper and lower bounds,Convex hull,Regular polygon,Convex polytope,Polytope,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
27 | 3 | 0179-5376 |
Citations | PageRank | References |
3 | 0.61 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Aviran | 1 | 14 | 4.08 |
| Shmuel Onn | 2 | 420 | 54.77 |