A Polynomial Time Algorithm for Vertex Enumeration and Optimization over Shaped Partition Polytopes

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-171674

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.