A Polynomial Time Algorithm for Shaped Partition Problems.
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.
Introduction
The Partition Problem concerns the partitioning of vectors A in d-space into p parts
so as to maximize an objective function which is convex on the sum of vectors in each part;
see [3]. Each vector A i represents d numerical attributes associated with the ith element
of the set ng to be partitioned. Each ordered partition -
is then associated with the d \Theta p matrix A
whose jth column
represents the total attribute vector of the jth part. The problem is to find an admissible
partition - which maximizes an objective function f given by
a real convex functional on IR d\Thetap . Of particular interest is the Shaped Partition Problem,
Department of Applied Mathematics, Chiaotung University, Hsinchu, 30045, Taiwan. Email address:
fhwang@math.nctu.edu.tw.
y William Davidson Faculty of Industrial Engineering and Management, Technion-Israel Institute of
Technology, 32000 Haifa, Israel. Email address: onn@ie.technion.ac.il. Research supported in part by the
Mathematical Sciences Research Institute at Berkeley California through NSF Grant DMS-9022140, by the
N. Haar and R. Zinn Research Fund at the Technion, and by the Fund for the Promotion of Research at
the Technion.
z William Davidson Faculty of Industrial Engineering and Management, Technion-Israel Institute of
Technology, 32000 Haifa, Israel. Email address: rothblum@ie.technion.ac.il. Research supported in part by
the E. and J. Bishop Research Fund at the Technion and by ONR Grant N00014-92-J1142.
Shaped partition problems
where the admissible partitions are those - whose shape (j- 1 lies in a prescribed
set   of admissible shapes. In this article we concentrate on this later situation.
The Shaped Partition Problem has applications in diverse fields that include circuit
layout, clustering, inventory, splitting, ranking, scheduling and reliability, see [5, 9, 14, 15]
and references therein. Further, as we demonstrate later on, the problem has expressive
power that captures NP-hard problems such as the Max-Cut problem and the Traveling
Salesman problem, even when the number p of parts or attribute dimension d are fixed.
Our first goal in this article is to demonstrate, constructively, that a polynomial time
algorithm for the Shaped Partition Problem does exist when both p and d are fixed. This
result is valid when the set   of admissible shapes and the function C are presented by
oracles. So, our first result (formally stated and proved in Section 4) is:
ffl Theorem 4.2: Any Shaped Partition Problem is solvable in polynomial oracle time
using O(n dp 2
operations and queries.
Our solution method is based on the observation that since C is convex, the Shaped Partition
Problem can be embedded into the problem of maximizing C over the Shaped Partition
A defined to be the convex hull of all matrices A - corresponding to partitions of
admissible shapes. The class of Shaped Partition Polytopes is very broad and generalizes
and unifies classical permutation polytopes such as Birkhoff's polytope and the Permuto-
hedron (see e.g. [8, 19, 21]). Its subclass of bounded shaped partition polytopes with lower
and upper bounds on the shapes was previously studied in [3], under the assumption that
the vectors A are distinct. Therein a polynomial procedure for testing whether
a given A - is a vertex of P
A was obtained. This procedure is simplified and extended
in [11]. A related but different generalization of classical permutation polytopes, arising
when algebraic (representation-theoretical) constraints, rather than shape constraints, are
imposed on the permutations involved, was studied in [19] and references therein.
Since a Shaped Partition Polytope is defined as the convex hull of an implicitly presented
set whose size is typically exponential in the input size even when both p and d are fixed,
an efficient representation as the convex hull of vertices or as the intersection of half-spaces
is not readily expected. Our second objective is to prove that, nevertheless, for fixed p and
d, the number of vertices of Shaped Partition Polytopes is polynomially bounded in n, and
that it is possible to explicitly enumerate all vertices in polynomial time. So, our second
result (formally stated and proved in Section 4) is:
ffl Theorem 4.3: Any Shaped Partition Polytope P
A has O(n
vertices which can be
produced in polynomial oracle time using O(n d 2 p 3
operations and queries.
An immediate corollary of Theorem 4.3 is that, for fixed d; p, the number of facets of P
A
is polynomially bounded as well and that all facets can be produced in polynomial oracle
time (Corollary 4.4). Theorem 4.3 shows, in particular, that it is possible to compute the
number of vertices efficiently. This might be extendible to the situation of variable d and
counting vertices is generally a hard task (cf. [16]), as is counting partitions with
various prescribed properties (see [4, 10]). The vertex counting problem for variable d and
p will be addressed elsewhere.
Frank K. Hwang, Shmuel Onn and Uriel G. Rothblum 3
A special role in our development is played by separable partitions, defined as partitions
where vectors in distinct sets are (weakly) separable by hyperplanes. In the special case
partitions had been studied quite extensively (see e.g. [2, 5, 7, 17]). The case
has also been considered quite recently in [6]. Here we study such partitions
for all d; p, as well as a class of generic partitions, and provide an upper bound on their
number and an algorithm for producing them. In our recent related work [1], the precise
extremal asymptotical behavior of such partitions is determined.
The embedding of the partition problem into the problem of maximizing the convex
function C over the partition polytope is useful due to the optimality of vertices in the
latter problem. When   consists of a single shape, the optimality of vertices holds for the
more general class of Asymmetric Schur convex function, introduced in [13]; see [8]. All of
our results apply with C as any asymmetric Schur convex function and   consisting of a
single shape.
The article is organized as follows. In the next section we formally define the Shaped
Partition Problem and Shaped Partition Polytope. We demonstrate the expressive power of
this problem by giving four examples. For the first two examples, in which the parameters
d; p are typically small and fixed, our Theorem 4.2 provides a polynomial time solution.
The last two examples show that the Max-Cut problem and Traveling Salesman problem
can be modeled as Shaped Partition Problems with fixed respectively, and
that the corresponding polytopes have exponentially many vertices. In Section 3 we study
separability properties of vertices of Shaped Partition Polytopes and discuss separable and
generic partitions. In the final Section 4 we use our preparatory results of Section 3 to
establish Theorems 4.2 and 4.3 and Corollary 4.4.
Shaped Partition Problems and Polytopes
A p-partition of [n] := ng is an ordered collection -
sets (possibly empty) whose union is [n]. A p-shape of n is a tuple
nonnegative integers
n. The shape of a p-partition - is the
p-shape of n given by j-j := (j- 1 j). If   is a set of p-shapes of n then a  -partition
is any partition - whose shape j-j is a member of  .
Let A be a real d \Theta n matrix; for to denote the ith column of A.
For each p-partition - of [n] we define the A-matrix of - to be the d \Theta p matrix
with
We consider the following algorithmic problem.
Shaped Partition Problem. Given positive integers d;
set   of p-shapes of n, and objective function on  -partitions given by
C convex on IR d\Thetap , find a  -partition -   which maximizes f , namely satisfies
4 Shaped partition problems
Of course, the complexity of this problem depends on the presentation of   and C. But, we
will construct algorithms that work in strongly polynomial time and can cope with minimal
information on   and C. Specifically, we assume that the set of admissible p-partitions
can be represented by a membership oracle which on query - answers whether or not - 2  .
The convex functional C on IR d\Thetap can be presented by an evaluation oracle that on query
A - with - a  -partition returns
Since C is convex, the Shaped Partition Problem can be embedded into the problem of
maximizing C over the convex hull of A-matrices of feasible partitions, defined as follows.
Shaped Partition Polytope. For a matrix A 2 IR d\Thetan and nonempty set   of p-shapes
of n we define the Shaped Partition Polytope P
A to be the convex hull of all A-matrices of
-partitions, that is,
A := conv
We point out that for any A, the polytope P
A is the image of the Shaped Partition Polytope
I , with I the n \Theta n identity, under the projection X 7! AX . In [12] this is exploited, for
the situation where the function C is linear and  is a set of bounded
shapes, to solve the corresponding Shaped Partition Problem for all n; d; p in polynomial
time by linear programming over P
I .
We now demonstrate the expressive power of the Shaped Partition Problem. In par-
ticular, we show that even if one of d or p is fixed, the Shaped Partition Problem may be
NP-hard, and the number of vertices of the Shaped Partition Polytope may be exponen-
tial. Therefore, polynomial time algorithms for optimization and vertex enumeration are
expected to (and, as we show, do) exist only when both d and p are fixed. We start with
two examples in which it is natural to have d; p small and fixed.
Example 2.1 Splitting. The n assets of a company are to be split among its p owners
as follows. For the jth owner prescribes a nonnegative vector A
entries represent the relative values of the various
assets to this owner. A partition - which splits the assets
among the owners and maximizes the l q -norm (
q of the total value vector
whose jth entry
A j;i is the total relative value of the assets allocated to the jth
owner by -. An alternative interpretation of the splitting problem concerns the division
of an estate consisting of n assets among p inheritors having equal rights against the es-
tate. With 2, the model captures a problem of a divorcing couple dividing their joint
Frank K. Hwang, Shmuel Onn and Uriel G. Rothblum 5
For fixed p, Theorem 4.2 asserts that we can find an optimal partition in polynomial time
O(n
while the number p n of  -partitions is exponential. We note that other (convex)
functions C can be used within our framework. In particular, if C is linear on IR p\Thetap
when our results of [12] apply and y ield a polynomial time solution even when p is
variable.
Example 2.2 Balanced Clustering. Given are objects represented by attribute
vectors A . The objects are to be grouped in p clusters, each containing
points, so as to to minimize the sum of cluster variance of a partition - given by
, where jj \Delta jj denotes the l 2 -norm and -
A j is
the barycenter of the ith cluster.
with
d
Here, we use the fact that
. For fixed d; p,
by Theorem 4.2 we can find an optimal balanced clustering in polynomial time O(n dp 2
while the number of  -partitions is
The next two examples show that unless both d; p are fixed, the Shaped Partition Problem
may be NP-hard. The idea is simple: the formulation is such that every  -partition -
gives a distinct vertex A - of the Shaped Partition Polytope P
A . Then, any function f on
-partitions factors as f(-) := convex C on P
A , say the one given by
In the following examples, the membership oracle for   and the evaluation oracle for f(-) :=
restricted to A-matrices, are easily polynomial time realizable from the natural data
for the problem.
Example 2.3 Max-Cut Problem and Unit Cube. Find a cut with maximum number
of crossing edges in a given graph E).
Here, the A-matrices of  -partitions are precisely all (0; 1)-valued n \Theta 2 matrices with each
row sum equals 1; in particular, each such matrix is determined by its first column. It
follows that the Shaped Partition Polytope P
A has 2 n vertices which stand in bijection
with  -partitions, and is affinely equivalent to the n-dimensional unit cube by projection
of matrices onto their first column. So, each A - is a distinct vertex of P
A and there is a
convex C on IR d\Theta2 such that
6 Shaped partition problems
Example 2.4 Travelling Salesman Problem and Permutohedron. Find a shortest
Hamiltonian path on n sites under a given symmetric nonnegative matrix D, where D i;j
represents the distance between sites i and j.
where we regard a partition simply as the corresponding permutation. The matrices A -
in this case are simply all permutations of A. The Shaped Partition Polytope P
A has n!
vertices which stand in bijection with  -partitions, and is the so-called Permutohedron.
Since each A - is a distinct vertex of P
A , there is again a convex C on IR n such that
3 Vertices and generic partitions
In this section we show that every vertex of any Shaped Partition Polytope P
A equals the
A-matrix A - of some A-generic partition, a notion that we introduce and develop below.
The convex hull of a subset U in IR d will be denoted conv(U ). Two finite sets U; V of
points in IR d are separable if there is a vector h 2 IR d such that h T
and with u 6= v; in this case, we refer to h as a separating vector of U and V . The
proof of the following characterization of separability is standard and is left to the reader.
It implies, in particular, that if U and V are separable then
Lemma 3.1 Let U and V be finite sets of IR d . Then U and V are separable if and only if
their convex hulls are either disjoint or intersect in a single point which is a common vertex
of both.
Let A be a given d \Theta n matrix. For a subset S ' [n] let A
the set of columns of A indexed by S (with multiple copies of columns identified). A p-
partition A-separable if the sets A -r and A -s are separable for each pair
that is, for each there is a vector h r;s 2 IR d such that
r;s A j for all We have the following lemma which
generalizes a result of [3] from matrices with no zero columns and no repeated columns.
Lemma 3.2 Let A be a matrix in IR d\Thetan , let   be a nonempty set of p-shapes of n, and let
- be a  -partition. If A - is a vertex of P
A then - is an A-separable partition.
Proof. The claim being obvious for suppose that p - 2. Let A - be a vertex of
A . Then there is a matrix C 2 IR d\Thetap such that the linear functional on IR d\Thetap given by
the inner product hC;
i is uniquely maximized over P
A at A - . Pick
any pair 1 . Suppose there are
with A i 6= A j (otherwise A -r and A -s are trivially separable). Let - 0 be the  -partition
obtained from - by switching i and j, i.e. taking - 0
Frank K. Hwang, Shmuel Onn and Uriel G. Rothblum 7
. By
choice of C we have hC; A - 0
r;s
This proves A -r ,A -s are separable for each pair 1 - r ! s - p, hence - is A-separable.
We need some more terminology. Let A 2 IR d\Thetan . A p-partition -
[n] is A-disjoint if are disjoint for each pair 1 - r ! s - p. As
the convex hulls of finite sets are disjoint if and only if the sets can be strictly separated
by a hyperplane, we have that - is A-disjoint if and only if for each
there exists a vector h r;s 2 IR d such that (h r;s
Of course, A-disjointness implies A-separability, and the two properties coincide when the
columns of A are distinct.
For the vector obtained by appending a first coordinate 1
to v. For a matrix A 2 IR d\Thetan and indices 1 -
sign A (i
A matrix A is generic if its columns are in affine general position, that is, if any set of d+ 1
vectors or less from among f -
ng are linearly independent; in particular, if
? d this is the case if and only if all signs sign A (i
are nonzero. Also, the columns of a generic matrix are distinct.
We next provide a representation of the set of A-disjoint 2-partitions for generic matrices
A. The case where n - d is simple.
Lemma 3.3 Let A 2 IR d\Thetan be generic, p - 2 and n - d. Then every p-partition of [n] is
A-disjoint.
Proof. It suffices to consider the case 2. A standard result from linear algebra shows
that as -
A n are linearly independent, the range of [ -
a 2-partition - of [n], there is a vector - 2 IR d+1 with - T A i ? 0 for each
for each obtained from - by truncating its first coordinate - 1 we then have
proving that - is A-disjoint.
Let A 2 IR d\Thetan be generic with n - d. For any d-subset I of [n] with
Of course, fI \Gamma
A g is a 2-partition of [n] n I . Let I ' [n] be a d-set and
2-partition of I . The 2-partitions of [n] associated with A; I and are defined to be
either of the two 2-partitions
Lemma 3.4 Let A 2 IR d\Thetan be generic with n - d. Then the set of A-disjoint 2-partitions
is the set of all 2-partitions associated with A, d-sets I ' [n] and 2-partitions
I.
8 Shaped partition problems
Proof. We will show that for each d-set I ' [n] and 2-partition I , the
two 2-partitions associated with A; I and are A-disjoint and that each A-disjoint
2-partition is generated in this way.
First, let I ' [n] have d-elements, say
of I . Then H
is a hyperplane that contains the
columns of A indexed by I ; this hyperplane can be written as fx 2
Thus, h T A
A . We next observe that
assures that the 2-partition
of [d] is B-disjoint. Thus, there exists a vector d 2 IR d with d T A i ? d T A j
for all . For sufficiently small positive t we then have that (C
proving that
A-disjoint. It follows immediately that
proving that
the two 2-partitions of [n] associated with A; I and 2-partition of I are A-disjoint.
Next assume that - is an A-disjoint 2-partition. Then there exists a hyperplane strictly
separating A - 1 and A - 2 . Any such hyperplane can be perturbed to a hyperplane that is
spanned by d columns of A and weakly separates A - 1 and A - 2 (the details of constructing
such a perturbation are left to the reader). In particular, if A span the hyperplane
A [ I
or
A [ I . In the former case we have
I and in the latter case
and
2. With each list [-
2-partitions of [n]
associate a p-tuple - of subsets of [n] as follows: for
of the p-tuple associated
with the given list are pairwise disjoint. If [ p
holds as well then - is a p-partition
which will be called the partition associated with the given list.
Lemma 3.5 For A 2 IR d\Thetan and p - 2, the set of A-disjoint p-partitions equals the set of
p-partitions associated with lists of
A-disjoint 2-partitions.
Proof. First, consider a p-partition - associated with a list of
Then for each
so - is A-disjoint. Conversely, let - be an A-disjoint p-partition. Consider
any pair 1 are disjoint, there is a hyperplane
H r;s which contains no column of A and defines two corresponding half spaces
r;s and H
r;s
that satisfy A -r ae H \Gamma
r;s and A -s ae H
r;s . Let - r;s := (- r;s
2 ) be the A-disjoint 2-partition
defined by - r;s
r;s g and - r;s
r;s g. Let - 0 be the
Frank K. Hwang, Shmuel Onn and Uriel G. Rothblum 9
p-tuple associated with the constructed - r;s 's. Then the sets of - 0 are pairwise disjoint and
we have
is the p-partition associated with the
constructed list of
A-disjoint 2-partitions.
For each ffl ? 0 define the ffl-perturbation A(ffl) 2 IR d\Thetan of A as follows: for
let the ith column of A(ffl) be A(ffl) i := A i
is the image of
i on the moment curve in IR d . Consider any 1 - n. Then the determinant
d
is a polynomial of degree d in ffl, with D d being the Van der Monde determinant
d ] which is known to be nonzero. So for all sufficiently small ffl ? 0,
sign A(ffl) (i the sign of the first nonzero coefficient among
d and is either \Gamma1 or 1 and independent of ffl. We define the generic sign of
A at (i as the common value of sign A(ffl) (i
sufficiently small positive ffl.
Lemma 3.6 Let A 2 IR d\Thetan and p - 1. For all sufficiently small ffl ? 0, A(ffl) is generic
and the set of A(ffl)-disjoint p-partitions is the same. Further, for every d-set I 2 [n], the
sets I \Gamma
A(ffl) and I
are independent of ffl.
Proof. By Lemma 3.5, the set of A(ffl)-disjoint p-partitions is entirely determined by the
set of A(ffl)-disjoint 2-partitions. Thus, it suffices to consider only 2.
First assume that n ! d. In this case augment A with vectors to obtain
a matrix A 0 2 IR d\Theta(d+1) . The above arguments show that for sufficiently small positive ffl,
det -
A 0 (ffl) is nonzero, implying that -
A(ffl) n are linearly independent. From Lemma
3.3 it follows that for such ffl, the set of A(ffl)-disjoint 2-partitions of [n] is the set of all
2-partitions of [n].
Next assume that n ? d. As explained above, for all sufficiently small ffl ? 0, sign A(ffl)
the nonzero generic sign -A (i It
follows that for all sufficiently small ffl, the matrix A(ffl) is generic and for every d-set I , the
sets I \Gamma
A(ffl) and I
are independent of ffl. By Lemma 3.4, the set of A(ffl)-disjoint 2-partitions
is the set of all pairs of 2-partitions of [n] associated with A; d-sets I ' [n] and 2-partitions
but each such pair depends only on I \Gamma
. Hence is the
same for all sufficiently small ffl ? 0.
Let A 2 IR d\Thetan . A p-partition of [n] is A-generic if it is A(ffl)-disjoint for all sufficiently
A the set of A-generic p-partitions.
Lemma 3.6 shows that for all sufficiently small ffl ? 0, the set of A(ffl)-disjoint partitions is
the same and equals \Pi p
A . The final lemma of this section links vertices of Shaped Partition
Polytopes with generic partitions.
Shaped partition problems
Lemma 3.7 Let A 2 IR d\Thetan and let   be a nonempty set of p-shapes of [n]. Then every
vertex of the polytope P
A has a representation as the A-matrix A - of some A-generic  -
partition.
Proof. Let d\Thetap be a vertex of P
A and let C 2 IR d\Thetap be a matrix such that hC; \Deltai
is uniquely maximized over P
A at B. Let \Pi \Lambdag be the set of  -partitions
and let \Pi   := f- Bg. Then there is a sufficiently small ffl ? 0 such that
in addition, as guaranteed by
Lemma 3.6, A(ffl) is generic and the set of A(ffl)-disjoint p-partitions equals \Pi p
A . For such
ffl hC; \Deltai is maximized over the perturbed polytope P
A(ffl) at a vertex of the form A(ffl) -
for
some -   2 \Pi   . By Lemma 3.2, -   is A(ffl)-separable. Since A(ffl) is generic it has distinct
columns and therefore -   is also A(ffl)-disjoint. We conclude that -   is A-generic, proving
that -   contains a generic partition.
4 Optimization and Vertex Enumeration
We now use the facts established in the previous section to prove our main results. Our
computational complexity terminology is fairly standard (cf. [20]). In all our algorithms,
the positive integer n will be input in unary representation, whereas all other numerical
data such as the matrix A will be input in binary representation. An algorithm is strongly
polynomial time if it uses a number of arithmetic operations polynomially bounded in n,
and runs in time polynomially bounded in n plus the bit size of all other numerical input.
Lemma 4.1 Let d; p be fixed. For any A 2 IR d\Thetan , the set \Pi p
A of A-generic p-partitions has
Further, there is an algorithm that, given n 2 IN and A 2 l
produces
A in strongly polynomial time using O(n dp 2
Proof. If n - d, the set of A-generic p-partitions is the set of all partitions, of which
there are p n - p d . Henceforth we assume that n ? d. If
A := f([n])g consists
of the single p-partition ([n]). Suppose now p - 2. For each choice 1 -
compute the generic sign -A (i Evaluate the polynomial
d
at Each evaluation involves the computation
of the determinant of a matrix of order d+1 and can be done, say by Gaussian elimination,
using O(d 3 ) arithmetic operations and, for rational A, in strongly polynomial time. Then,
solve the following linear system of equations
d
to obtain the indeterminates D . This can be done by inverting the nonsingular Van
der Monde matrix of coefficients of this system, again by Gaussian elimination. The generic
Frank K. Hwang, Shmuel Onn and Uriel G. Rothblum 11
sign -A (i is then the sign of the first nonzero D i . So, for fixed d the number of
operations needed to compute all
signs is O
By Lemma 3.6, for sufficiently small positive ffl, for each d-set I ' [n], I \Gamma
A(ffl) and I
are
independent of ffl. For a d-set I ' [n] and such ffl, I \Gamma
A(ffl) and I
are available from the above
signs that determine det[ -
permutation that puts -
into the right location may be applied). Further, from Lemma 3.6 and 3.4, \Pi 2
A equals the
common set of A(ffl)-disjoint partitions for sufficiently small positive ffl, and this set is the
set of partitions of [n] of the form
is a d-subset of [n] and 2-partition of I . For each d-set I ' [n], the common
2-partitions
sufficiently small positive ffl has been determined; hence a list of
the 2-partitions in \Pi 2
A is available (the construction may contain duplicates). As there are
d
d-subsets I and 2 d 2-partitions of each I , we have j\Pi 2
d
all partitions in \Pi 2
A can be obtained from the generic signs using again O(n d+1 ) operations.
For sufficiently small positive ffl, \Pi p
A is the common set of A(ffl)-disjoint p-partitions and
A is the common set of A(ffl)-disjoint 2-partitions. It follows from Lemma 3.5 that \Pi p
A is
the set of all p-partitions associated with lists of
2-partitions from \Pi 2
A . This shows that
To construct \Pi p
A , produce all such lists of
2-partitions from \Pi 2
A ; for each list form the
associated p-tuple -, and test if it is a partition (i.e. if [ p
[n]). As there are O(n
lists, all this work can be easily done using O(n dp 2
operations which subsumes
the work for computing the generic signs and constructing \Pi 2
A , and is the claimed bound.
We can now provide the solution of the Shaped Partition Problem. The set of admissible
p-partitions   can be represented by a membership oracle which on query - answers whether
or not - 2  . The convex functional C on IR d\Thetap can be presented by an evaluation oracle
that on query A - with - a  -partition returns The oracle for C will be called
M-guaranteed if guaranteed to be a rational number whose absolute value is no
larger than M for any  -partition -. The algorithm is then strongly polynomial oracle time
if it uses a number of arithmetic operations and oracle queries polynomially bounded in n,
and runs in time polynomially bounded in n plus the bit size of A and M .
Theorem 4.2 For every fixed d; p there is an algorithm that, given n; M 2 IN, A 2 l
oracle presented nonempty set   of p-shapes of n, and M-guaranteed oracle presented convex
functional C on l
solves the Shaped Partition Problem in strongly polynomial oracle
time using O(n dp 2
operations and oracle queries.
Proof. Use the algorithm of Lemma 4.1 to construct the set \Pi p
A of A-generic p-partitions
in strongly polynomial time using O(n dp 2
test shapes of the
partitions in the list to obtain the subset \Pi   := f- 2 \Pi p
\Lambdag of A-generic  -
partitions by querying the  -oracle on each of the j\Pi p
partitions in \Pi p
A . Since
C is convex, it is maximized over the Shaped Partition Polytope P
A at a vertex of P
A .
Shaped partition problems
By Lemma 3.7, this vertex equals the A-matrix A - of some partition in \Pi   . Therefore,
any -   2 \Pi   achieving
is an optimal solution to
the Shaped Partition Problem. To find such -   compute for each - 2 \Pi   the matrix
, query the C-oracle for the value pick the best.
The number of operations involved and queries to the C-oracle is again O(n dp 2
). The bit
size of the numbers manipulated throughout this process is polynomially bounded in the
bit size of M and A hence the algorithm is strongly polynomial oracle time.
Recall that the Shaped Partition Polytope is defined as P
\Lambdag.
The number of matrices in the set fA \Lambdag is typically exponential in n, even
for fixed d; p. Therefore, although the dimension of P
A is bounded by dp, this polytope
can potentially have exponentially many vertices and facets as well. But, Lemmas 3.7 and
4.1 yield the following theorem which shows that, in fact, Shaped Partition Polytopes are
exceptionally well behaved.
Theorem 4.3 Let d; p be fixed. For any A 2 IR d\Thetan and nonempty set   of p-shapes of n,
the number of vertices of the Shaped Partition Polytope P
A is O(n d( p) ). Further, there is
an algorithm that, given n 2 IN, A 2 l
presented  , produces all vertices of
A in strongly polynomial oracle time using O(n d 2 p 3
operations and queries.
Proof. By Lemma 3.7, each vertex of P
A equals the A-matrix A - of some partition in
A . Therefore, the number of vertices of P
A is bounded above by j\Pi p
A j hence, by Lemma
4.1, is O(n
To construct the set of vertices given a rational matrix A, proceed as fol-
lows. Use the algorithm of Lemma 4.1 to construct the set \Pi p
A of A-generic p-partitions in
strongly polynomial time using O(n dp 2
operations. Test the shapes of the partitions
in the list to obtain its subset \Pi   := f- 2 \Pi p
\Lambdag of A-generic  -partitions by
querying the  -oracle on each of the j\Pi p
partitions in \Pi p
A . Construct the set
of matrices U := fA - 2 \Pi   g with multiple copies identified. This set U is contained in
A and by Lemma 3.7 contains the set of vertices of P
A . So u 2 U will be a vertex precisely
when it is not a convex combination of other elements of U . This could be tested using
any linear programming algorithm, but to obtain a strongly polynomial time procedure,
we proceed as follows. By Carath'eodory's theorem, u will be a vertex if and only if it is
not in the convex hull of any affine basis of U n fug. So, to test if u 2 U is a vertex of P
A ,
compute the affine dimension a of U n fug. For each (a of U n fug,
test if it is an affine basis of U n fug, and if it is compute the unique -
P a
P a
in the convex hull of fu if and only
a vertex of P
A if and only if for each affine basis we get some
Computing the affine dimension a, testing if an (a+1)-subset of U nfug is an affine
basis and computing the - i , can all be done by Gaussian elimination in strongly polynomial
time. Since we have to perform the entire procedure for each of the jU j - j\Pi
elements for each such u the number of affine bases of U nfug is at most
the number of arithmetic operations involved is O(jU j
which absorbs
the work for constructing \Pi   and obeys the claimed bound.
Frank K. Hwang, Shmuel Onn and Uriel G. Rothblum 13
As an immediate corollary of Theorem 4.3, we get the following polynomial bound on
the number of facets of any Shaped Partition Polytope and a strongly polynomial oracle
time procedure for producing all facets (by which we mean finding, for each facet F , a
supporting P
A at F ).
Corollary 4.4 Let d; p be fixed. For any A 2 IR d\Thetan and nonempty set   of p-shapes of n,
the number of facets of the Shaped Partition Polytope P
A is O(n d 2 p 3
Further, there is an
algorithm that, given n 2 IN, A 2 l
presented  , produces all facets of P
A
in strongly polynomial oracle time using O(n d 2 p 3
operations and queries.
Proof. By the well known Upper Bound Theorem [18], the number of facets of any
k-dimensional polytope with m vertices is O(m k
Applying this to P
A with k - dp and
get the bound on the number of facets of P
A . To construct the facets,
construct first the set V of vertices using the algorithm of Theorem 4.3. Compute the
dimension a of aff(P (possibly empty) set S of dp \Gamma a points
that together with V affinely span IR d\Thetap . For each affinely independent a-subset T of V ,
compute the hyperplane fX 2 spanned by S [ T . This hyperplane
supports a facet of P
A if and only if all points in V lie on one of its closed half-spaces.
Clearly, all facets of P
A are obtained that way, in strongly polynomial time and number of
arithmetic operations and oracle queries bounded as claimed.

Acknowledgment

Shmuel Onn thanks the Mathematical Sciences Research Institute at Berkeley for its support
while part of this research was done.



--R

Discrete Applied Mathematics
A simple on-line randomized incremental algorithm for computing higher order (Voronoi) diagrams
Optimal partitions having disjoint convex and conic hulls
Mathematics of Operations Research
Consecutive optimizers for a partitioning problem with applications to optimal inventory groupings for joint replenish- ment
Cutting dense point sets in half
The Art of Counting (edited by Joel Spencer)
Partition polytopes over 1- dimensional points
The Pareto set of the partition bargaining game
Journal of Combinatorial Theory Ser.
Representations and characterizations of the vertices of bounded-shape partition polytopes
Linear programming over partitions

Partitions: Clustering and Optimality
SIAM Journal on Algebraic and Discrete Mathematics
Discrete and Computational Geometry.
On the number of halving lines
The maximum numbers of faces of a convex polytope.

Theory of Linear and Integer Programming
Lectures in Polytopes
--TR

--CTR
Uli Wagner, On the number of corner cuts, Advances in Applied Mathematics, v.29 n.2, p.152-161, August 2002
Sharon Aviran , Nissan Lev-Tov , Shmuel Onn , Uriel G. Rothblum, Vertex characterization of partition polytopes of bipartitions and of planar point sets, Discrete Applied Mathematics, v.124 n.1-3, p.1-15, 15 December 2002
Babson , Shmuel Onn , Rekha Thomas, The Hilbert zonotope and a polynomial time algorithm for universal Grbner bases, Advances in Applied Mathematics, v.30 n.3, p.529-544, April
F. K. Hwang , J. S. Lee , Y. C. Liu , U. G. Rothblum, Sortability of vector partitions, Discrete Mathematics, v.263 n.1-3, p.129-142, 28 February
polynomial time;optimization;polytope;convex;programming;enumeration;partition;separation;cluster