Monotone Optimal Multipartitions Using Schur Convexity with Respect to Partial Orders
Authors:
- Frank K. HwangFHFrank K. Hwang
- Uriel G. RothblumURUriel G. Rothblum
- Larry SheppLSLarry Shepp
- 1 November 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 6 (4) , 533-547
Abstract
In a $( t,n,m )$-multipartitioning problem, t lists of $nm$ ordered numbers are partitioned into n sets, where each set contains m numbers from each list. The goal is to maximize some objective function that depends on the sum of the elements in each set and is called the partition function. The authors use the recently developed theory of majorization and Schur convexity with respect to partially ordered sets to study optimal multipartitions for the above problem. In particular, they apply the results to construct a class of counterexamples to a recent conjecture of Du and Hwang, which asserts that (classic) Schur convex functions can be characterized as the partition functions for $( 1,n,m )$-multipartitioning problems having monotone optimal solutions.
Keywords
This publication has 10 references indexed in Scilit:
- Optimality of Monotone Assemblies for Coherent Systems Composed of Series ModulesOperations Research, 1994
- Majorization and Schur Convexity with Respect to Partial OrdersMathematics of Operations Research, 1993
- When is greedy module assembly optimal?Naval Research Logistics (NRL), 1990
- Optimal Assembly of an s-Stage k-Out-of-n SystemSIAM Journal on Discrete Mathematics, 1990
- Optimal assembly of systems using schur functions and majorizationNaval Research Logistics (NRL), 1987
- Majorization and the Lorenz Order: A Brief Introduction1987
- Majorization of Finite Partially Ordered SetsSIAM Journal on Algebraic Discrete Methods, 1982
- Majorization on a partially ordered setProceedings of the American Mathematical Society, 1979
- Functions Decreasing in Transposition and Their Applications in Ranking ProblemsThe Annals of Statistics, 1977
- On optimal assembly of systemsNaval Research Logistics Quarterly, 1972