A Polynomial Time Algorithm for Shaped Partition Problems
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 10 (1), 70-81
- https://doi.org/10.1137/s1052623497344002
Abstract
We consider the class of shaped partition problems of partitioning n given vectors in d-dimensional criteria 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. This class has broad expressive power and captures NP-hard problems even if either d or p is fixed. In contrast, we show that when both d and p are fixed, the problem can be solved in strongly polynomial time. Our solution method relies on studying the corresponding class of shaped partition polytopes. Such polytopes may have exponentially many vertices and facets even when one of d or p is fixed; however, we show that when both d and p are fixed, the number of vertices of any shaped partition polytope is $O(n^{d{p\choose 2}})$ and all vertices can be produced in strongly polynomial time.
Keywords
This publication has 15 references indexed in Scilit:
- Partition polytopes over 1-dimensional pointsMathematical Programming, 1999
- Separable partitionsDiscrete Applied Mathematics, 1999
- Representations and characterizations of vertices of bounded-shape partition polytopesLinear Algebra and its Applications, 1998
- Colourful Linear Programming and its RelativesMathematics of Operations Research, 1997
- Cutting dense point sets in halfDiscrete & Computational Geometry, 1997
- Enumerating nested and consecutive partitionsJournal of Combinatorial Theory, Series A, 1995
- A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMSInternational Journal of Computational Geometry & Applications, 1992
- Optimal partitions having disjoint convex and conic hullsMathematical Programming, 1992
- The Pareto set of the partition bargaining problemGames and Economic Behavior, 1991
- Consecutive Optimizers for a Partitioning Problem with Applications to Optimal Inventory Groupings for Joint ReplenishmentOperations Research, 1985