A POLYNOMIAL TIME ALGORITHM FOR VERTEX ENUMERATION AND OPTIMIZATION OVER SHAPED

PARTITION POLYTOPES

FRANK K. HWANG, SHMUEL ONN, AND URIEL G. ROTHBLUM

Abstract. We consider the 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 Shaped Partition Polytope defined as the convex hull of solutions. The Shaped Partition Problem captures N 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\binom{p}{2}}) vertices which can be enumerated in O(n^{k^{2}p^{3}}) arithmetic operations, and that any Shaped Partition Problem is solvable in O(n^{kp^{2}}) arithmetic operations.

1. Introduction

The Partition Problem concerns the partitioning of vectors A^{1}, …, A^{n} in k-space into p parts so as to maximize an objective function which is convex on the sum of vectors in each part. Each vector A^{i} represents k numerical attributes associated with the ith element of the set [n] = {1, …, n} to be partitioned. Each ordered partition π = (π_{1}, …, π_{p}) of [n] is then associated with the k × p matrix A^{π} = [∑_{i∈π_{1}} A^{i}, …, ∑_{i∈π_{p}} A^{i}] 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 f(π) = C(A^{π}) where C is a real convex functional on IR^{k×p}. Of particular interest is the Shaped Partition Problem, where the admissible partitions are those π whose shape (|π_{1}|, …, |π_{p}|) 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

The research of Shmuel Onn was supported by the Mathematical Sciences Research Institute at Berkeley California through NSF Grant DMS-9022140, and by Two Technion VPR Grants.

The research of Uriel G. Rothblum was supported by the E. and J. Bishop Research Fund at the Technion and by ONR Grant N00014-92-J1142.

[3, 4, 6, 11] and references therein. As we demonstrate later on, the problem has expressive power that captures N P-hard problems such as the Max-Cut problem and the Traveling Salesperson problem, even when the number p of parts or attribute dimension k are fixed.

Our first goal in this article is to show that a polynomial time algorithm for the Shaped Partition Problem does exist when both p and k are fixed. This result remains valid when the set Λ of admissible shapes and the function C are presented by oracles (see Section 4 for the precise statement):

• Theorem 4.6: Any Shaped Partition Problem is solvable in oracle time O(n^{kp^{2}}).

Since C is convex, the Shaped Partition Problem can be embedded into the problem of maximizing C over the Shaped Partition Polytope P_{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 Permutohedron (see e.g. [15]). Its subclass of bounded shape partition polytopes with lower and upper bounds on the shapes was previously studied in [1], under the assumption that the vectors A^{1}, …, A^{n} are distinct. Therein a procedure for testing whether a given A^{π} is a vertex of P_{A}^{Λ} was obtained. This procedure is simplified and extended in [10]. A related but different important generalization of classical permutation polytopes, arizing when algebraic (representation-theoretical) constraints, rather than shape constraints, are enforced on the permutations involved, was studied in [15] 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 k are fixed, neither a presentation as the convex hull of vertices nor as the intersection of halfspaces is readily available for it. Our second objective is to bypass this difficulty by proving that, nevertheless, for fixed p and k, the number of vertices of Shaped Partition Polytopes is polynomially bounded in n, and it is possible to explicitly enumerate all vertices in polynomial time (see Section 4 for the precise statements):

• Theorem 4.3: Any Shaped Partition Polytope P_{A}^{Λ} has O(n^{(k+1)\binom{p}{2}}) vertices.

While this bound suffices for our algorithmic considerations in this article, we point out that in [9] we establish the more accurate bound of O(n^{k\binom{p}{2}}) on the number of vertices.

• Theorem 4.5: All vertices of P_{A}^{Λ} can be enumerated in oracle time O(n^{k^{2}p^{3}}).

A POLYTIME ALGORITHM FOR SHAPED PARTITION PROBLEMS AND POLYTOPES 3

In particular, it is possible to compute the number of vertices efficiently. This might be extendible to the situation of variable k and p, while counting vertices is generally a hard task (see [12, 13]), as is counting partitions with various prescribed properties (see [2]). The vertex counting problem for variable k and p will be addressed elsewhere.

The article is organized as follows. In the next section we formally define the Shaped Partition Problem and Shaped Partition Polytope. We demonstrate that the Max-Cut problem and Traveling Salesperson problem can be modeled as Shaped Partition Problems with fixed p = 2 and k=1, respectively, and that the corresponding polytopes have exponentially many vertices. In Section 3 we establish a sequence of lemmas in preparation for Section 4. We extend earlier results of [1] and provide a necessary condition for A^{π} to be a vertex of P_{A}^{Λ}. This leads to the study of partitions of points in space whose convex hulls are pairwise separable (in the special case k = p = 2 such partitions had been studied quite extensively, see e.g. [14]; the case k = 3, p = 2 has also been considered quite recently in [5]). In the final Section 4 we reward our preparatory results of Section 3 and establish Theorems 4.3, 4.5, and 4.6.

2. Shaped Partition Problems and Shaped Partition Polytopes

For a matrix A, we use A^{i} to denote its ith column. A p-partition of [n] := {1, …, n} is an ordered collection π = (π_{1}, …, π_{p}) of p (possibly empty) sets whose disjoint union is [n]. A p-shape of n is a tuple λ = (λ_{1} …, λ_{p}) of nonnegative integers λ_{1} …, λ_{p} satisfying ∑_{i=1}^{p} λ_{i} = n. The shape of a partition π is |π| := (|π_{1}|, …, |π_{p}|). If Λ is a set of p-shapes of n then a Λ-partition is any partition π whose shape |π| is a member of Λ.

Let A be a real k × n matrix. For each p-partition π of [n] we define the A-matrix of π to be the k × p matrix

A^{π} = [ ∑_{i∈π_{1}} A^{i}, …, ∑_{i∈π_{p}} A^{i}] ,

where ∑_{i∈π_{j}} A^{i} := 0 whenever π_{j} = ∅. We consider the following algorithmic problem.

Shaped Partition Problem. Given positive integers p, k, n, matrix A ∈ IR^{k×n}, nonempty set Λ of p-shapes of n, and objective function on Λ-partitions given by f(π) = C(A^{π}) with C convex on IR^{k×p}, find a Λ-partition π^{∗} which maximizes f, namely satisfies

f(π^{∗}) = max{f(π) : |π| ∈ Λ}.

The complexity of this problem depends on the presentation of Λ and C and on whether real arithmetic computations or Turing machine computations on rational data are assumed. Pleasantly, our algorithms work in strongly polynomial time and can cope with minimal information on Λ and C. So both Λ and C may be presented by oracles. All that is needed of an oracle for Λ is that on query shape λ it answers whether or not λ ∈ Λ. All that is needed of an oracle for C is that on query A^{π} it answers with C(A^{π}).

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 ∈ IR^{k×n} 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

P_{A}^{Λ} := conv {A^{π} : |π| ∈ Λ} ⊂ IR^{k×p}.

We point out that P_{A}^{Λ} is the image of the Shaped Partition Polytope P_{I}^{Λ}, with I the n × n identity, under the projection X ↦ A · X. In [8] this is exploited, for the situation where the function C is linear and Λ = {λ : l ≤ λ ≤ u} is a set of bounded shapes, to solve the corresponding Shaped Partition Problem for all n, p, k in polynomial time by linear programming over P_{I}^{Λ}, and to efficiently test for a given partition π whether A^{π} is a vertex of P_{A}^{Λ}.

Next we demonstrate that, even when either k or p are fixed, the Shaped Partition Problem may be N P-hard, and the number of vertices of the Shaped Partition Polytope may be exponential. Therefore, polynomial time algorithms for optimization and vertex enumeration may (and, as we show, do) exist only when both k and p are fixed.

Example 2.1. Max-Cut Problem and Unit Cube. Fix p = 2. Let Λ be the set of all 2-shapes of n, let k = n and let A be the n×n identity matrix. The A-matrices of Λ-partitions in this case are precisely all (0, 1)-valued n × 2 matrices with each row sum equals 1. 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. Now let G = ([n], E) be an undirected graph, and define an objective function f_{G} as follows: for a 2-partition π = (π_{1}, π_{2}) of [n] let f_{G}(π) = |{e ∈ E : |e ∩ π_{1}| = 1}| be the number of edges in the cut of G defined by π. Since each A^{π} is a distinct vertex of P_{A}^{Λ}, there is a convex C on IR^{k×2} such that f_{G}(π) = C(A^{π}) for all π. The Shaped Partition Problem in this case is precisely the Max-Cut problem of finding a largest cut in a graph hence is N P-hard.

Example 2.2. Travelling Salesperson Problem and Permutohedron. Fix k = 1. Let p = n, let Λ = {1^{n}} consist of the single shape 1^{n} = (1, …, 1), and let A = [1, 2, …, n]. 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. Now let D ∈ IR^{n×n} be a symmetric nonnegative matrix, where D_{i,j} represents the distance between locations i and j.

Define an objective function f_{D} as follows. For partition π = ({i_{1}}, …, {i_{n}}) let f_{D}(π) = − ∑_{j=1}^{n} D_{i_{j},i_{j+1}} be minus the length of the Traveling Salesperson Tour on [n] given by π (with i_{n+1} := i_{1}). Since each A^{π} is a distinct vertex of P_{A}^{Λ}, there is a convex C on IR^{n} such that f_{D}(π) = C(A^{π}) for all π. The Shaped Partition Problem in this case is precisely the Traveling Salesperson Problem of finding a shortest tour hence is N P-hard.

We finish this section with an example demonstrating how our results enable a polynomial time solution procedure which bypasses the need for checking the exponentially many feasible solutions present.

Example 2.3. Splitting. The n assets of a company are to be split among its p owners as follows. For i = 1, …, p, the ith owner prescribes a nonnegative vector A_{i} = (A_{i,1}, …, A_{i,n}) with ∑_{j=1}^{n} A_{i,j} = 1, whose entries represent the relative values of the various assets to this owner. A partition π = (π_{1}, …, π_{p}) is sought which splits the assets among the owners as evenly as possible, and maximizes the l_{q}-norm (∑_{i=1}^{p} | ∑_{j∈π_{i}} A_{i,j}|^{q})^{\frac{1}{q}} of the vector whose ith entry ∑_{j∈π_{i}} A_{i,j} is the total relative value of the assets handed to the ith owner by π. This can be formulated as a Shaped Partition Problem with k = p, the p × n matrix A whose rows are the A_{i}, the set Λ of all p-shapes λ of n with ⌊\frac{n}{p}⌋ ≤ λ_{i} ≤ ⌈\frac{n}{p}⌉ for all i, and objective function f_{q}(π) = C_{q}(A^{π}) where C_{q} is the convex function on IR^{p×p} defined by C_{q}(M) = ∑_{i=1}^{p} |M_{i,i}|^{q}. For fixed p, by Theorem 4.6 we can find an optimal partition in polynomial time O(n^{p^{3}}), while the number of partitions is exponential Ω(p^{n}n^{\frac{1−p}{2}} ). We note further that for q = 1 the functional C_{1} is linear on IR_{+}^{p×p} hence our results of [8] apply and yield a polynomial time solution even when p is variable.

3. Preparation

In this section we establish a sequence of lemmas in preparation for the final section. Two finite sets U, V of points in IR^{k} will be called separable if there is a vector h ∈ IR^{k} such that h^{T} u < h^{T} v for all u ∈ U and v ∈ V with u ≠ v. It is not hard to see that U, V are separable if and only if their convex hulls conv(U) and conv(V) are either disjoint or intersect in a single point which is a common vertex of both. In particular, if U and V are separable then |U ∩ V | ≤ 1.

Let A be a given k × n matrix. For a subset S ⊆ [n] let A^{S} = {A^{i} : i ∈ S} be the set of columns of A indexed by S (with multiple copies of columns identified). A p-partition π = (π_{1}, …, π_{p}) will be called A-separable if the sets A^{π_{r}} and A^{π_{s}} are separable for each pair 1 ≤ r < s ≤ p. So π is A-separable if for each pair 1 ≤ r < s ≤ p there is a vector h_{r,s} ∈ IR^{k} such that h_{r,s}^{T}A^{i} < h_{r,s}^{T}A^{j} for all i ∈ π_{r} and j ∈ π_{s} with A^{i} ≠ A^{j}. We have the following lemma which, for a matrix A with distinct nonzero columns, specializes to a result of [1].

Lemma 3.1. Let A be a matrix in IR^{k×n}, 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 p = 1, suppose that p ≥ 2. Let A^{π} be a vertex of P_{A}^{Λ}. Then there is a matrix C ∈ IR^{k×p} such that the linear functional on IR^{k×p} given by the inner product ⟨C, X⟩ = ∑_{i=1}^{k} ∑_{j=1}^{p} C_{i}^{j}X_{i}^{j} is uniquely maximized over P_{A}^{Λ} at A^{π}. Pick any pair 1 ≤ r < s ≤ p, and let h_{r,s} = C^{s} − C^{r}. Suppose there are i ∈ π_{r} and j ∈ π_{s} with A^{i} ≠ A^{j} (otherwise A^{π_{r}} and A^{π_{s}} are trivially separable). Let π′ be the Λ-partition obtained from π by switching i and j, i.e. taking π′_{r} := π_{r} ∪ {j} \ {i}, π′_{s} := π_{s}∪{i}\{j}, and π′_{t} := π_{t} for all t ≠ r, s. Then (A^{π′})^{r} = (A^{π})^{r}+A^{j}−A^{i} ≠ (A^{π})^{r} hence A^{π′} ≠ A^{π}. By choice of C we have ⟨C, A^{π′}⟩ < ⟨C, A^{π}⟩ and so

h_{r,s}^{T}(A^{j} − A^{i}) = (C^{s} − C^{r})^{T} (A^{j} − A^{i}) = ∑_{t=1}^{p}(C^{t})^{T} ((A^{π})^{t} − (A^{π′})^{t}) = ⟨C, A^{π} − A^{π′}⟩ > 0.

This proves that A^{π_{r}} and A^{π_{s}} are separable for each pair 1 ≤ r < s ≤ p, hence π is A-separable.

Let A be a k × n matrix. A p-partition π = (π_{1}, …, π_{p}) will be called A-disjoint if conv(A^{π_{r}}) and conv(A^{π_{s}}) are disjoint for each pair 1 ≤ r < s ≤ p. Also, for A ∈ IR^{k×n} let \underline{A} be the matrix obtained by appending a new row [1, …, n] to A.

Lemma 3.2. Let A ∈ IR^{k×n} and let \underline{A} be as above. For each A-separable partition π there exists an \underline{A}-disjoint partition \underline{π} of the same shape |\underline{π}| = |π| satisfying A^{π} = A\underline{π}.

Proof. Let π = (π_{1}, …, π_{p}) be any A-separable p-partition. As any 1-partition is both separable and disjoint, we may assume p ≥ 2. Let \underline{π} be the lexicographically first partition for which \{A^{\underline{π}^{i}}\} = \{A^{π_{i}}\} for i = 1, …, p, where \{A^{S}\} stands for the multiset of columns of A indexed by S. More precisely, \underline{π} is the partition such that for all u ∈ IR^{k} the following hold: if we put U_{i} := {j ∈ π_{i} : A^{j} = u} and \underline{U}_{i} := \{j ∈ \underline{π}_{i} : A^{j} = u\}, then |\underline{U}_{i}| = |U_{i}| for all i = 1, …, p, and i < j for all i ∈ \underline{U}_{r} and j ∈ \underline{U}_{s} with 1 ≤ r < s ≤ p. By definition \underline{π} has the same shape as π and satisfies A\underline{π} = A^{π}.

Now consider any pair 1 ≤ r < s ≤ p. Since π is A-separable, there is a vector h_{r,s} ∈ IR^{k} such that h_{r,s}^{T}A^{i} < h_{r,s}^{T}A^{j} for all i ∈ π_{r} and j ∈ π_{s} with A^{i} ≠ A^{j}. Let \underline{h}_{r,s} be the (k + 1)-vector obtained by appending a last coordinate ϵ to h_{r,s}, with ϵ > 0 sufficiently small. For i ∈ \underline{π}_{r} and j ∈ \underline{π}_{s} consider the quantity

\underline{h}_{r,s}^{T}(\underline{A}^{j} − \underline{A}^{i}) = h_{r,s}^{T}(A^{j} − A^{i}) + ϵ(j − i);

if A^{i} ≠ A^{j} then, since ϵ is infinitesimal, this quantity is positive; if A^{i} = A^{j} then, by choice of \underline{π}, i < j and this quantity is again positive. So conv(A^{\underline{π}^{r}}) and conv(A^{\underline{π}^{s}}) are disjoint. It follows that \underline{π} is \underline{A}-disjoint and the proof is complete.

For v ∈ IR^{k} denote by v̄ the (k +1)-vector obtained by appending a first coordinate 1 to v. An orientation of a hyperplane H is a presentation of H as the zero set H = {x ∈ IR^{k} : h^{T} x̄ = 0} of a linear form (with h ∈ IR^{k+1}). With an orientation of H, the closed and open halfspaces H^{≤}, H^{<} below it are distinguishable from the ones H^{≥}, H^{>} above it. The hyperplane H spanned by an ordered list [v^{1}, …, v^{k}] of k affinely independent points in IR^{k} will be oriented as H = {x ∈ IR^{k} : det[v̄^{1}, …, v̄^{k}, x̄] = 0}.

A matrix A will be called generic if its columns are in affine general position. Let A ∈ IR^{k×n} be generic with n > k. With each triple (I, J^{<}, J^{>}) where I is a k-subset of [n] and (J^{<}, J^{>}) is a 2-partition of I, we associate two A-disjoint 2-partitions π^{<} and π^{>} as follows. Let [A^{I}] denote the list of columns of A indexed by I and ordered as in A. Let H := aff([A^{I}]) be the hyperplane spanned by A^{I} oriented by the ordered list [A^{I}]. Let I^{<} := {i ∈ [n] : A^{i} ∈ H^{<}} and I^{>} := {i ∈ [n] : A^{i} ∈ H^{>}}. Define π^{<} := (I^{<}∪J^{<}, I^{>}∪J^{>}) and π^{>} := (I^{>}∪J^{>}, I^{<}∪J^{<}). Both π^{<} and π^{>} are A-disjoint since H can be slightly perturbed so as to strictly separate A^{π_{1}} and A^{π_{2}}.

Lemma 3.3. Let A ∈ IR^{k×n} be generic. The set of A-disjoint 2-partitions is the set of all 2-partitions if n ≤ k and is the set of partitions associated with triples (I, J^{<}, J^{>}) as above if n > k.

Proof. If n ≤ k then the columns of A are affinely independent hence conv(A^{π_{1}}) and conv(A^{π_{2}}) are disjoint for any 2-partition π. Suppose now n > k and let π = (π_{1}, π_{2}) be any A-disjoint 2-partition. Since conv(A^{π_{1}}) and conv(A^{π_{2}}) are disjoint, a standard separation result assures the existence of a hyperplane spanned by columns of A such that A^{π_{1}} is contained in one of its closed halfspaces and A^{π_{2}} in the other. Since A is generic, this hyperplane H contains exactly k columns of A, so that H = aff(A^{I}) for some k-subset I of [n]. If the orientation aff([A^{I}]) of H is such that A^{π_{1}} ⊂ H^{≤} and A^{π_{2}} ⊂ H^{≥} then π is the partition π^{<} associated with the triple (I, I ∩ π_{1}, I ∩ π_{2}), whereas if A^{π_{2}} ⊂ H^{≤} and A^{π_{1}} ⊂ H^{≥} then π is the partition π^{>} associated with the triple (I, I ∩ π_{2}, I ∩ π_{1}).

Let now A ∈ IR^{k×n} be an arbitrary matrix. Define for each ϵ > 0 a perturbation A(ϵ) ∈ IR^{k×n} of A as follows: for i = 1, …, n let the ith column of A(ϵ) be A(ϵ)^{i} := A^{i} + ϵM_{k}^{i} where M_{k}^{i} := [i, i^{2}, …, i^{k}]^{T} is the image of i on the moment curve in IR^{k}.

Definition 3.4. Let A ∈ IR^{k×n} and p ≥ 1. A p-partition π of [n] will be called A-generic if it is A(ϵ)-disjoint for all sufficiently small ϵ > 0. The set of A-generic p-partitions will be denoted by Π_{A}^{p}.

Lemma 3.5. Let A ∈ IR^{k×n} and p ≥ 1. For all sufficiently small ϵ > 0, the perturbation A(ϵ) is generic and the set of A(ϵ)-disjoint p-partitions contains the set of A-disjoint p-partitions and is independent of ϵ and equals Π_{A}^{p}.

Proof. Regard the entries of A(ϵ) as linear forms in ϵ. Recall that v̄ denotes the (k + 1)-vector obtained by appending a first coordinate 1 to v ∈ IR^{k}. Suppose first that n > k. Then each determinant det[Ā(ϵ)^{i_{0}}, …, Ā(ϵ)^{i_{k}}] is a polynomial of degree k in ϵ whose leading coefficient is the nonzero Van der Monde determinant det[M̄_{k}^{i_{0}}, …, M̄_{k}^{i_{k}}], hence has finitely many zeroes. So for all sufficiently small ϵ > 0 all of these determinants are nonzero hence A(ϵ) is generic. For n ≤ k the same argument applies by restricting attention to the first n rows of A.

Next consider any A-disjoint p-partition π. The claim being obvious for p = 1, suppose that p ≥ 2. For each pair 1 ≤ r < s ≤ p, there is a hyperplane which strictly separates A^{π_{r}} and A^{π_{s}}. Clearly, for all sufficiently small ϵ this hyperplane also strictly separates A(ϵ)^{π_{r}} and A(ϵ)^{π_{s}}, so π is also A(ϵ)-disjoint.

Finally, we show that for all sufficiently small ϵ > 0 the set of A(ϵ)-disjoint ppartitions is the same. We start with the case p = 2. If n ≤ k then by Lemma 3.3 this set simply consists of all 2-partitions. So assume that n > k. Let I = {i_{1}, …, i_{k}} be any k-subset of [n] with i_{1} < ⋯ < i_{k}. For each i ∉ I, consider the following determinant, which is again a nonzero polynomial of degree k in ϵ:

D^{i}(ϵ) := det[Ā(ϵ)^{i_{1}}, …, Ā(ϵ)^{i_{k}}, Ā(ϵ)^{i}] = ∑_{j=0}^{k} D_{j}^{i}ϵ^{j}.

For all sufficiently small ϵ > 0 the sign of D^{i}(ϵ) equals the sign of the first nonzero coefficient among D_{0}^{i}, …, D_{k}^{i} and is either positive or negative and independent of ϵ. Denote this generic sign by sign(D^{i}). Then I^{<} = {i ∈ [n] : sign(D^{i}) < 0} and I^{>} = {i ∈ [n] : sign(D^{i}) > 0} are independent of ϵ and therefore for each 2-partition (J^{<}, J^{>}) of I, the partitions π^{<}, π^{>} associated with the triple (I, J^{<}, J^{>}) are independent of ϵ. So the set of partitions associated with triples (I, J^{<}, J^{>}) is the same for all small ϵ > 0 and by Lemma 3.3 this is the set of A(ϵ)-disjoint 2partitions. Now consider any p-partition π with p ≥ 2 arbitrary. Consider any pair 1 ≤ r < s ≤ p, and restrict attention to the submatrix [A^{π_{r}∪π_{s}}] of A consisting of the columns of A indexed by π_{r} ∪ π_{s}. The same determinantal argument as in the paragraph above shows that for all sufficiently small ϵ the 2-partition (π_{r}, π_{s}) of π_{r} ∪ π_{s} is either [A(ϵ)^{π_{r}∪π_{s}}]-disjoint or not independently of ϵ. So conv(A(ϵ)^{π_{r}}) and conv(A(ϵ)^{π_{s}}) are either disjoint or not independently of ϵ. Since this hold for each pair 1 ≤ r < s ≤ p, we see that π is either A(ϵ)-disjoint or not independently of ϵ as claimed.

Let p ≥ 2. With each list [π^{r,s} = (π_{1}^{r,s}, π_{2}^{r,s}) : 1 ≤ r < s ≤ p] of \binom{p}{2} 2-partitions of [n] associate a p-tuple π = (π_{1}, …, π_{p}) of subsets of [n] as follows: for i = 1, …, p put

π_{i} := (∩_{j=i+1}^{p}π_{1}^{i,j}) ⋂ (∩_{j=1}^{i−1}π_{2}^{j,i}) .

Since π_{r} ⊆ π_{1}^{r,s} and π_{s} ⊆ π_{2}^{r,s} for all 1 ≤ r < s ≤ p, the π_{i} are pairwise disjoint. If also ∪_{i=1}^{p}π_{i} = [n] then π is a partition, and will be called the partition associated with the given list. If moreover each π^{r,s} is A-disjoint, then so is π.

Lemma 3.6. For A ∈ IR^{k×n} and p ≥ 2, the set of A-disjoint p-partitions equals the set of p-partitions associated with lists of \binom{p}{2} A-disjoint 2-partitions.

Proof. Let π = (π_{1}, …, π_{p}) be an A-disjoint p-partition. Consider any pair 1 ≤ r < s ≤ p. Since conv(A^{π_{r}}) and conv(A^{π_{s}}) are disjoint, there exists an oriented hyperplane H_{r,s} which contains no column of A and satisfies A^{π_{r}} ⊂ H_{r,s}^{<} and A^{π_{s}} ⊂ H_{r,s}^{>}. Let π^{r,s} := (π_{1}^{r,s}, π_{2}^{r,s}) be the A-disjoint 2-partition defined by π_{1}^{r,s} := {i ∈ [n] : A^{i} ∈ H_{r,s}^{<}} and π_{2}^{r,s} := {i ∈ [n] : A^{i} ∈ H_{r,s}^{>}}. Let π′ be the p-tuple associated with the π^{r,s}. Then the π′ are pairwise disjoint and for i = 1, …, p we have

π_{i} ⊆ (∩_{j=i+1}^{p}π_{1}^{i,j}) ⋂ (∩_{j=1}^{i−1}π_{2}^{j,i}) = π′_{i}.

Since [n] = ∪_{i=1}^{p}π_{i} ⊆ ∪_{i=1}^{p}π′_{i}, it follows that π = π′ is the p-tuple associated with the constructed list of \binom{p}{2} A-disjoint 2-partitions.

Lemmas 3.5 and 3.6 imply our final preparatory lemma.

Lemma 3.7. For A ∈ IR^{k×n} and p ≥ 2, the set Π_{A}^{p} of A-generic p-partitions equals the set of p-partitions associated with lists of \binom{p}{2} A-generic 2-partitions.

Proof. By Lemma 3.5 there is an ϵ such that Π_{A}^{2} equals the set of A(ϵ)-disjoint 2-partitions and Π_{A}^{p} equals the set of A(ϵ)-disjoint p-partitions. The lemma follows by applying Lemma 3.6 to A(ϵ).

4. Vertex Enumeration and Optimization

We now use the facts established in the previous section to provide an upper bound on the number of vertices of any Shaped Partition Polytope. We then proceed to give efficient algorithms for the enumeration of these vertices and for the solution of the Shaped Partition Problem.

Lemma 4.1. For any A ∈ IR^{k×n} and positive integer p, the number of A-generic p-partitions satisfies |Π_{A}^{p}| = O(n^{k\binom{p}{2}}).

Proof. If p = 1 the bound is trivial so assume p ≥ 2. By Lemma 3.5 and Lemma 3.3 applied to the perturbation A(ϵ) with ϵ sufficiently small, if n ≤ k then Π_{A}^{2} consists of all 2^{n} = O(2^{k}) = O(n^{k}) 2-partitions, whereas if n > k then it contains at most two associated partitions per triple (I, J^{<}, J^{>}) with I a k-subset of [n] and (J^{<}, J^{>}) a 2-partition of I. So |Π_{A}^{2}| is at most twice the number 2^{k}\binom{n}{k} of such triples. By

Lemma 3.7, the set Π_{A}^{p} contains at most one partition per each list of \binom{p}{2} partitions from Π_{A}^{2}, hence, as claimed,

|Π_{A}^{p}| ≤ |Π_{A}^{2}|^{\binom{p}{2}} ≤ (2^{k+1}\binom{n}{k})^{\binom{p}{2}} = O(n^{k\binom{p}{2}}).

For A ∈ IR^{k×n} and nonempty set Λ of p-shapes let Π_{A}^{Λ} be the subset of Π_{A}^{p} of Ageneric Λ-partitions. For A ∈ IR^{k×n} let \underline{A} be obtained as before by appending a new row [1, …, n] to A.

Lemma 4.2. Let A ∈ IR^{k×n} and let Λ be a nonempty set of p-shapes of n. Any vertex of P_{A}^{Λ} equals the A-matrix A^{π} of some partition π in ΠΛ ; \underline{A}.

Proof. Consider any vertex A^{π} of P_{A}^{Λ}. By Lemma 3.1, the Λ-partition π is Aseparable. By Lemma 3.2, there is another Λ-partition \underline{π} such that A^{π} = A\underline{π} and \underline{π} is \underline{A}-disjoint. By Lemma 3.5, \underline{π} ∈ Πp ; \underline{A} hence is in ΠΛ ; \underline{A}.

We can now conclude an upper bound on the number of vertices of any Shaped Partition Polytope, which suffices for our purposes here. In [9] we use a more delicate argument which is based on treating the multisets of columns of A in the original space, without lifting to (k+1)-space, and derive the more accurate bound of O(n^{k\binom{p}{2}}) on the number of vertices.

Theorem 4.3. For any A ∈ IR^{k×n}, positive integer p and nonempty set Λ of p-shapes of n, the number of vertices of the Shaped Partition Polytope P_{A}^{Λ} is O(n^{(k+1)\binom{p}{2}}).

Proof. Let \underline{A} be as above. By Lemmas 4.1 and 4.2 above,

|vert(P_{A}^{Λ})| ≤ |ΠΛ ; \underline{A}| ≤ |Πp ; \underline{A}| = O(n^{(k+1)\binom{p}{2}}).

Note that this theorem stands in contrast with the fact that typically the number of Λ-partitions is exponential in n even for fixed p.

We next describe an algorithm for the enumeration of Π_{A}^{p}.

Lemma 4.4. There is an algorithm that, given positive integers p, k, n and a matrix A ∈ IR^{k×n}, enumerates the set Π_{A}^{p} of A-generic p-partitions using O(p^{2} · n^{k\binom{p}{2}+1}) real arithmetic operations. For rational A and fixed p and k this is a strongly polynomial time algorithm.

Proof. If p = 1 then let Π_{A}^{p} := {([n])} consists of the single p-partition ([n]). Suppose now p ≥ 2. First, we describe how to produce the set Π_{A}^{2} of A-generic 2-partitions. For each ϵ > 0 let A(ϵ) ∈ IR^{k×n} be a perturbation of A obtained, as before, by setting A(ϵ)^{i} := A(ϵ)^{i} + ϵM_{k}^{i}, and let Ā(ϵ)^{i} be obtained, as before, by appending a first coordinate 1 to A(ϵ)^{i}. If n ≤ k then, by Lemma 3.3, Π_{A}^{2} consists of all 2^{n} = O(2^{k}) = O(n^{k}) 2-partitions. Suppose now n > k. Let I = {i_{1}, …, i_{k}} be any k-subset of [n] with i_{1} < ⋯ < i_{k}. For each i ∉ I let

D^{i}(ϵ) := det [Ā(ϵ)^{i_{1}}, …, Ā(ϵ)^{i_{k}}, Ā(ϵ)^{i}] = ∑_{j=0}^{k} D_{j}^{i}ϵ^{j}.

As explained in the proof of Lemma 3.5, D^{i}(ϵ) is a nonzero polynomial of degree k in ϵ whose sign D^{i}(ϵ) is the same generic sign sign(D^{i}) for all sufficiently small ϵ > 0 and equals the sign of the first nonzero coefficient among D_{0}^{i}, …, D_{k}^{i}. To compute these coefficients, substitute ϵ = 0, …, k and compute each of the numerical determinants D^{i}(0), …, D^{i}(k). Then solve the system of linear equations ∑_{j=0}^{k} ϵ^{j}D_{j}^{i} = D^{i}(ϵ), ϵ = 0, …, k in the indeterminates D_{0}^{i}, …, D_{k}^{i}. Since the defining matrix of this system is a Van der Monde matrix hence nonsingular, D_{0}^{i}, …, D_{k}^{i} are uniquely determined and so is sign(D^{i}). Each of the numerical determinants D^{i}(ϵ) can be computed, and the system of equations solved, by Gaussian Elimination which takes O(k^{3}) arithmetic operations. So each sign(D^{i}) is computable in O(k^{4}) operations. Therefore I^{<} = {i ∈ [n] : sign(D^{i}) < 0} and I^{>} = {i ∈ [n] : sign(D^{i}) > 0} are computable in O(nk^{4}) operations, as are the two 2-partitions π^{<} and π^{>} associated with each triple (I, J^{<}, J^{>}). As there are 2^{k}\binom{n}{k} such triples, the set Π_{A}^{2} of A-generic 2-partitions can

be computed in 2^{k}\binom{n}{k}nk^{4} = O(n^{k+1}) operations.

To construct Π_{A}^{p}, produce, using O(p^{2}n) operations, from each list of \binom{p}{2} partitions from Π_{A}^{2}, the associated p-tuple π. Then test if it is a partition (i.e. if ∪_{i=1}^{p}π_{i} = [n]). As there are at most (2^{k}\binom{n}{k})^{\binom{p}{2}} such lists, the total number of arithmetic operations is

bounded by p^{2}n(2^{k}\binom{n}{k})^{\binom{p}{2}} = O(p^{2}·n^{k\binom{p}{2}+1}) which subsumes the work for constructing Π_{A}^{2} and is the claimed bound. Lemma 3.7 guarantees that each A-generic p-partition of shape Λ is included. The claim about rational data follows from the fact that Gaussian Elimination admits a strongly polynomial time algorithm (see e.g. [16]).

We can now provide the algorithm for the vertex enumeration of any Shaped Partition Polytope. It suffices for the algorithm that the set of shapes Λ (whose size may be exponential in the rest of the data) is presented by an oracle that on query shape λ answers whether or not λ ∈ Λ.

Theorem 4.5. There is an algorithm that, given positive integers p, k, n, matrix A ∈ IR^{k×n}, and an oracle presentation of a nonempty set Λ of p-shapes of n, enumerates the set of vertices of the Shaped Partition Polytope P_{A}^{Λ} using O(n^{k^{2}p^{3}}) real arithmetic operations and oracle queries. For rational A and fixed p and k this is a strongly polynomial time oracle algorithm.

Proof. Let \underline{A} ∈ IR^{(k+1)×n} be as before. Use the algorithm of Lemma 4.4 applied to \underline{A} to construct the set of \underline{A}-generic p-partitions Πp ; \underline{A}. For each partition π in this set, test if it is a Λ-partition by querying the Λ-oracle about its shape |π|. In this way, produce the set ΠΛ ; \underline{A} of \underline{A}-generic Λ-partitions. Then construct the set of k × p matrices U := \{A^{π} : π ∈ ΠΛ ; \underline{A}\} with multiple copies identified. This set U is contained in P_{A}^{Λ} and by Lemma 4.2 contains the set of vertices of P_{A}^{Λ}. So u ∈ U will be a vertex precisely when it is not a convex combination of other elements of U. Testing it is a Linear Programming problem. To solve it, we shall appeal to Carathéodory’s theorem and exhaustive search rather than invoke an LP-algorithm.

This allows to deal with real data and, for rational data and fixed k, p, obtain a strongly polynomial time procedure. So to test if u ∈ U is a vertex of P_{A}^{Λ} do the following. Let d := dim(aff(U \ \{u\})) ≤ kp + 1. For each of the \binom{|U|−1}{d} subsets {u_{1}, …, u_{d}} of U \ {u}, check if it is an affine basis of aff(U \ {u}) by checking if dim(ū_{1}, …, ū_{d}) = d; if it is, obtain the unique expression ū = ∑_{i=1}^{d} μ_{i}ū_{i} of u as affine combination of the u_{i}. If μ_{1}, …, μ_{d} ≥ 0 then u is in fact a convex combination of the u_{i} hence not a vertex of P_{A}^{Λ}. So u is a vertex of P_{A}^{Λ} if and only if for each affine basis we get some μ_{i} < 0. To compute d, to compute dim(ū_{1}, …, ū_{d}), and to solve for the μ_{i}, use Gaussian Elimination again.

By Lemma 4.4 applied to \underline{A}, the set Πp ; \underline{A} can be constructed in O(n^{(k+1)p^{2}}) opera-

tions. The number of oracle queries is |Πp ; \underline{A}| = O(n^{(k+1)\binom{p}{2}}), as guaranteed by Lemma

4.1, and the number of matrices in U satisfies |U| ≤ |ΠΛ ; \underline{A}| ≤ |Πp ; \underline{A}| = O(n^{(k+1)\binom{p}{2}}). As the effort of constructing ΠΛ ; \underline{A} is absorbed in the vertex testing procedure, we have that the total number of arithmetic operations and oracle queries is bounded by |U|\binom{|U|−1}{kp+1}(kp + 1)^{3} = O(n^{k^{2}p^{3}}) as claimed. The claim for rational data follows from the strongly polynomial time computability of Gaussian Elimination.

Finally, we provide an algorithmic solution of the Shaped Partition Problem we started with. It suffices that the convex functional C is presented by an oracle that on query A^{π} with π a Λ-partition answers with C(A^{π}). The oracle for C will be called M-guaranteed if C(A^{π}) is guaranteed to be a rational number whose binary encoding is no longer than M bits for any Λ-partition π.

Theorem 4.6. There is an algorithm that, given positive integers p, k, n, matrix A ∈ IR^{k×n}, an oracle presentation of a nonempty set Λ of p-shapes of n, and an oracle presentation of a convex functional C on IR^{k×p}, solves the Shaped Partition Problem of finding a Λ-partition π^{∗} which maximizes f(π) = C(A^{π}) using O(n^{kp^{2}}) real arithmetic operations and oracle queries. For rational A, fixed p and k, and M-guaranteed oracle for C, the running time of this oracle algorithm is strongly polynomial in n, M and the bit size of A.

Proof. Let \underline{A} be as before. Use the algorithm of Lemma 4.4 applied to \underline{A} to construct the set of partitions Πp ; \underline{A}, using O(p^{2} · n^{(k+1)\binom{p}{2}+1}) arithmetic operations. Then filter out its subset ΠΛ ; \underline{A} of \underline{A}-generic Λ-partitions by querying the Λ-oracle on each

of the |Πp ; \underline{A}| = O(n^{(k+1)\binom{p}{2}}) partitions in Πp ; \underline{A}. Since C is convex, there will be an optimal Λ-partition π for the Shaped Partition Problem for which A^{π} is a vertex of P_{A}^{Λ}, hence, by Lemma 4.2, an optimal π ∈ ΠΛ ; \underline{A}. For each π ∈ ΠΛ ; \underline{A} compute A^{π} (using O(kn) operations) and query the C-oracle for the value C(A^{π}). Pick π^{∗} to be the one attaining maximum value. The number of operations and queries to the Λ-oracle and C-oracle is bounded, as claimed, by O(kn · n^{(k+1)\binom{p}{2}}) + O(p^{2} · n^{(k+1)\binom{p}{2}+1}) = O(n^{kp^{2}}).

For rational data, since the C-oracle is M-guaranteed, each of the comparisons of its answers needed to determine the optimal π^{∗} is doable in time linear in M. Since Π_{A}^{Λ} is strongly polynomial time computable for fixed p, k, the claim about strongly polynomial time solution of the Shaped Partition Problem follows.

Acknowledgment

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

References

[1] E.R. Barnes, A.J. Hoffman and U.G. Rothblum, Optimal partitions having disjoint convex and conic hulls, Mathematical Programming, 54:69–86, 1992.

[2] I. Bárány and S. Onn, Colourful linear programming and its relatives, Mathematics of Operations Research, 20 pages, to appear.

[3] V. Capoyleas, G. Rote and G. Woeginger, Geometric Clusterings, Journal of Algorithms, 12:341-356, 1991.

[4] A.K. Chakravarty, J.B. Orlin and U.G. Rothblum, Consecutive optimizers for a partitioning problem with applications to optimal inventory groupings for joint replenishment, Operations Research, 33:820–834, 1985.

[5] H. Edelsbrunner, P. Valtr and E. Welzl, Cutting dense point sets in half, Proceedings of the ACM Symposium on Computational Geometry, 10:203–210, 1994.

[6] D. Granot and U.G. Rothblum, The Pareto set of the partition bargaining game, Games and Economic Behavior, 3:163–182, 1991.

[7] F.K. Hwang, C.L. Mallows, Enumerating nested and consecutive partitions, Journal of Combinatorial Theory Ser. A, 70:323–333, 1995.

[8] F.K. Hwang, S. Onn and U.G. Rothblum, Optimization over partitions I: linear programming, manuscript.

[9] F.K. Hwang, S. Onn and U.G. Rothblum, Polynomial enumeration of the vertices of constrained-shape partition-polytopes, submitted.

[10] F.K. Hwang, S. Onn and U.G. Rothblum, Representations and characterizations of the vertices of bounded-shape partition polytopes, submitted.

[11] F.K. Hwang, J. Sun and E.Y. Yao, Optimal set partitioning, SIAM Journal on Algebraic and Discrete Mathematics, 6:163–170, 1985.

[12] P. Kleinschmidt and S. Onn, Signable posets and partitionable simplicial complexes, Discrete and Computational Geometry., 15:443–466, 1996.

[13] N. Linial, Hard enumeration problems in geometry and combinatorics, SIAM Journal on Algebraic and Discrete Mathematics, 7:331–335, 1986.

[14] L. Lovász, On the number of halving lines, Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica 14:107–108, 1970.

[15] S. Onn, Geometry, complexity, and combinatorics of permutation polytopes, Journal of Combinatorial Theory Ser. A, 64:31-49, 1993.

[16] A. Schrijver, Theory of Linear and Integer Programming, John Wiley, New York, 1986.

Frank K. Hwang, Department of Applied Mathematics, Chaiotung University, Hsinshu, Taiwan.

Shmuel Onn, Department of Operations Research, Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, 32000 Haifa, Israel.

Uriel G. Rothblum, Department of Operations Research, Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, 32000 Haifa, Israel.