Mathematics – Combinatorics
Scientific paper
1997-04-29
Mathematics
Combinatorics
Scientific paper
We consider the {\em Shaped Partition Problem} of partitioning $n$ given vectors in real $k$-space into $p$ parts so as to maximize an arbitrary objective function which is convex on the sum of vectors in each part, subject to arbitrary constraints on the number of elements in each part. In addressing this problem, we study the {\em Shaped Partition Polytope} defined as the convex hull of solutions. The Shaped Partition Problem captures ${\cal N}{\cal P}$-hard problems such as the Max-Cut problem and the Traveling Salesperson problem, and the Shaped Partition Polytope may have exponentially many vertices and facets, even when $k$ or $p$ are fixed. In contrast, we show that when both $k$ and $p$ are fixed, the number of vertices is polynomial in $n$, and all vertices can be enumerated and the optimization problem solved in strongly polynomial time. Explicitly, we show that any Shaped Partition Polytope has $O(n^{k{p\choose 2}})$ vertices which can be enumerated in $O(n^{k^2p^3})$ arithmetic operations, and that any Shaped Partition Problem is solvable in $O(n^{kp^2})$ arithmetic operations.
Hwang Frank K.
Onn Shmuel
Rothblum Uriel G.
No associations
LandOfFree
A Polynomial Time Algorithm for Vertex Enumeration and Optimization over Shaped Partition Polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Polynomial Time Algorithm for Vertex Enumeration and Optimization over Shaped Partition Polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Polynomial Time Algorithm for Vertex Enumeration and Optimization over Shaped Partition Polytopes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-171674