## Abstract

Consider the problem of partitioning n nonnegative numbers into p parts, where part i can be assigned n_{i} numbers with n_{i} lying in a given range. The goal is to maximize a Schur convex function F whose i th 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 (n _{1},..., n_{p}) 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.

Original language | English |
---|---|

Pages (from-to) | 321-339 |

Number of pages | 19 |

Journal | Journal of Combinatorial Optimization |

Volume | 11 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2006 May 1 |

## Keywords

- Bounded-shape partition
- Optimal partition
- Schur convex function
- Sum partition

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics