One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions

    loading  Checking for direct PDF access through Ovid


Consider the problem of partitioning n nonnegative numbers into p parts, where part i can be assigned ni numbers with ni lying in a given range. The goal is to maximize a Schur convex function F whose ith argument is the sum of numbers assigned to part i.

The shape of a partition is the vector consisting of the sizes of its parts, further, a shape (without referring to a particular partition) is a vector of nonnegative integers (n1,…, np) which sum to n. A partition is called size-consecutive if there is a ranking of the parts which is consistent with their sizes, and all elements in a higher-ranked part exceed all elements in the lower-ranked part. We demonstrate that one can restrict attention to size-consecutive partitions with shapes that are nonmajorized, we study these shapes, bound their numbers and develop algorithms to enumerate them. Our study extends the analysis of a previous paper by Hwang and Rothblum which discussed the above problem assuming the existence of a majorizing shape.

Related Topics

    loading  Loading Related Articles