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

Frank K. Hwang, Shmuel Onn, Uriel G. Rothblum

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…