The mean-partition problem. (English) Zbl 1131.90049
Summary: In mean-partition problems the goal is to partition a finite set of elements, each associated with a \(d\)-vector, into \(p\) disjoint parts so as to optimize an objective, which depends on the averages of the vectors that are assigned to each of the parts. Each partition is then associated with a \(d \times p\) matrix whose columns are the corresponding averages and a useful approach in studying the problem is to explore the mean-partition polytope, defined as the convex hull of the set of matrices associated with feasible partitions.
References:
| [1] | Alon N., Onn S. (1999) Separable partitions. Discrete Appl. Math. 91, 39–51 · Zbl 0926.05011 · doi:10.1016/S0166-218X(98)00142-5 |
| [2] | Anily S., Federgruen A. (1991) Structured partitioning problems. Oper. Res. 39, 130–149 · Zbl 0747.90080 · doi:10.1287/opre.39.1.130 |
| [3] | Barnes E.R., Hoffman A.J., Rothblum U.G. (1992) Optimal partitions having disjoint convex and conic hulls. Math. Prog. 54, 69–86 · Zbl 0751.90068 · doi:10.1007/BF01586042 |
| [4] | Chang F.H., Hwang F.K. (2005) Supermodularity in mean-partition problems. J. Global Optim. 33, 337–347 · Zbl 1093.90086 · doi:10.1007/s10898-004-7391-z |
| [5] | Chang G.J., Chen F.L., Huang L.L., Hwang F.K., Nuan S.T., Rothblum U.G., Sun I.F., Wang J.W., Yeh H.G. (1999) Sortabilities of partition properties. J. Comb. Optim. 2, 413–427 · Zbl 0955.90114 · doi:10.1023/A:1009737108224 |
| [6] | Gao B., Hwang F.K., Li W.W-C., Rothblum U.G. (1999) Partition-polytopes over 1-dimensional points. Math. Prog. 85, 335–362 · Zbl 0955.90116 · doi:10.1007/s101070050060 |
| [7] | Hwang F.K., Liao J.S., Chen C.Y. (2000) Supermodularity of various partition problems. J. Global Optim. 18, 275–282 · Zbl 1016.90078 · doi:10.1023/A:1008397707916 |
| [8] | Hwang F.K., Onn S., Rothblum U.G. (1999) A polynomial time algorithm for shaped partition problems. SIAM J. of Opt. 10, 70–81 · Zbl 0955.90118 · doi:10.1137/S1052623497344002 |
| [9] | Hwang F.K., Onn S., Rothblum U.G. (2000) Explicit solution of partitioning problems over a one-dimensional parameter space. Nav. Res. Logist. 47, 531–540 · Zbl 0977.90042 · doi:10.1002/1520-6750(200009)47:6<531::AID-NAV6>3.0.CO;2-K |
| [10] | Hwang F.K., Rothblum U.G. (1996) Directional-quasi-convexity, asymmetric Schur-convexity and optimality of consecutive partitions. Math. Oper. Res. 21, 540–554 · Zbl 0866.26008 · doi:10.1287/moor.21.3.540 |
| [11] | Hwang, F.K., Rothblum, U.G.: Partitions: optimality and clustering. World Scientific, London, New York, Singapore (2005), to appear |
| [12] | Marshall A.W., Olkin I. (1979) Inequalties, Theory of Majorization and its Applications. Academic Press, New York · Zbl 0437.26007 |
| [13] | Shapley L.S. (1971) Cores of convex games. Int. J. Game Theory 1, 11–26 · Zbl 0222.90054 · doi:10.1007/BF01753431 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
