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

F. H. Chang, H. B. Chen, Jun-Yi 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

Fingerprint

Objective function
Partition
Consecutive
Schur-convex Function
Non-negative
Partitioning
Ranking
Exceed
Maximise
Integer
Range of data
Demonstrate

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

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.

In: Journal of Combinatorial Optimization, Vol. 11, No. 3, 01.05.2006, p. 321-339.

Research output: Contribution to journalArticle

Chang, F. H. ; Chen, H. B. ; Guo, Jun-Yi ; Hwang, F. K. ; Rothblum, Uriel G. / One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions. In: Journal of Combinatorial Optimization. 2006 ; Vol. 11, No. 3. pp. 321-339.
@article{d2ce60adc0a748a8bd9760563d59c5f5,
title = "One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions",
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.",
keywords = "Bounded-shape partition, Optimal partition, Schur convex function, Sum partition",
author = "Chang, {F. H.} and Chen, {H. B.} and Jun-Yi Guo and Hwang, {F. K.} and Rothblum, {Uriel G.}",
year = "2006",
month = "5",
day = "1",
doi = "10.1007/s10878-006-7911-5",
language = "English",
volume = "11",
pages = "321--339",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "3",

}

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 -