### 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 |

### Fingerprint

### 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

### Cite this

*Journal of Combinatorial Optimization*,

*11*(3), 321-339. https://doi.org/10.1007/s10878-006-7911-5

**One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions.** / Chang, F. H.; Chen, H. B.; Guo, Jun-Yi; Hwang, F. K.; Rothblum, Uriel G.

Research output: Contribution to journal › Article

*Journal of Combinatorial Optimization*, vol. 11, no. 3, pp. 321-339. https://doi.org/10.1007/s10878-006-7911-5

}

TY - JOUR

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

AU - Chang, F. H.

AU - Chen, H. B.

AU - Guo, Jun-Yi

AU - Hwang, F. K.

AU - Rothblum, Uriel G.

PY - 2006/5/1

Y1 - 2006/5/1

N2 - 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 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,..., 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.

AB - 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 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,..., 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.

KW - Bounded-shape partition

KW - Optimal partition

KW - Schur convex function

KW - Sum partition

UR - http://www.scopus.com/inward/record.url?scp=33646582602&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646582602&partnerID=8YFLogxK

U2 - 10.1007/s10878-006-7911-5

DO - 10.1007/s10878-006-7911-5

M3 - Article

AN - SCOPUS:33646582602

VL - 11

SP - 321

EP - 339

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 3

ER -