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

F. H. Chang, H. B. Chen, J. Y. Guo, F. K. Hwang, Uriel G. Rothblum

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Pages (from-to)321-339
Number of pages19
JournalJournal of Combinatorial Optimization
Volume11
Issue number3
DOIs
Publication statusPublished - 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

Fingerprint Dive into the research topics of 'One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions'. Together they form a unique fingerprint.

  • Cite this