Partition-optimization with Schur convex sum objective functions

被引:33
作者
Hwang, FK [1 ]
Rothblum, UG
机构
[1] Chiaotung Univ, Dept Appl Math, Hsinchu 30045, Taiwan
[2] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
关键词
partitions; optimization; Schur-convexity;
D O I
10.1137/S0895480198347167
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We study optimization problems over partitions of the finite set N = {1,..., n}, where each element i in the partitioned set N is associated with a real number θ(i) and the objective associated with a partition ρ = (π(1),..., π(p)) has the form F(π) = f(θ(π)), where θ(π) = (Σ(i∈π 1) θ(i),..., Σ(i∈π p) θ(i)). When F is to be either maximized or minimized, we obtain conditions that allow for simple constructions of partitions that are uniformly optimal for all Schur convex functions f.
引用
收藏
页码:512 / 524
页数:13
相关论文
共 8 条
  • [1] Partition polytopes over 1-dimensional points
    Gao, B
    Hwang, FK
    Li, WCW
    Rothblum, UG
    [J]. MATHEMATICAL PROGRAMMING, 1999, 85 (02) : 335 - 362
  • [2] Directional-quasi-convexity, asymmetric Schur-convexity and optimality of consecutive partitions
    Hwang, FK
    Rothblum, UG
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 1996, 21 (03) : 540 - 554
  • [3] A polynomial time algorithm for shaped partition problems
    Hwang, FK
    Onn, S
    Rothblum, UG
    [J]. SIAM JOURNAL ON OPTIMIZATION, 1999, 10 (01) : 70 - 81
  • [4] HWANG FK, IN PRESS PARTITIONS
  • [5] Knuth D., 1981, ART COMPUTER PROGRAM
  • [6] Marshall Albert W., 1979, INEQUALITIES THEORY, V143
  • [7] LEAST D-MAJORIZED NETWORK FLOWS WITH INVENTORY AND STATISTICAL APPLICATIONS
    VEINOTT, AF
    [J]. MANAGEMENT SCIENCE SERIES A-THEORY, 1971, 17 (09): : 547 - 567
  • [8] VEINOTT AF, IN PRESS D MAJORIZAT