Browsing by Author "Chang, FH"

Now showing 1 - 4 of 4

One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions
(2006-05-01)
Chang, FH
;
Chen, HB
;
Guo, JY
;
Hwang, FK
;
Rothblum, UG
Consider the problem of partitioning n nonnegative numbers into p parts, where part i can be assigned n(i) numbers with n(i) lying in a given range. The goal is to maximize a Schur convex function F whose ith 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),..., n(p)) 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.
Supermodularity in mean-partition problems
(2005-11-01)
Chang, FH
;
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
Supermodularity of the lambda function which defines a permutation polytope has proved to be crucial for the polytope to have some nice fundamental properties. Supermodularity has been established for the lambda function for the sum-partition problem under various models. On the other hand, supermodularity has not been established for the mean-partition problem even for the most basic labeled single-shape model. In this paper, we fill this gap and also settle for all other models except one. We further extend our results to other types of supermodularity.
Wide-sense nonblocking for multi-log(d) N networks under various routing strategies
(2006-03-07)
Chang, FH
;
Guo, JY
;
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
Chang et al. showed that the number of middle switches required for WSNB under strategies: save the unused, packing, minimum index, cyclic dynamic, and cyclic static, for the 3-stage Clos network C(n, m, r) with r >= 3 is the same as required for SNB. In this paper, we prove the same conclusion for the multi-log(d) N network. We also extend our results, except for the minimum index strategy, to a general class of networks including the 3-stage Clos network and the multi-log(d) N network as special cases. (c) 2005 Elsevier B.V. All rights reserved.
Wide-sense nonblocking for symmetric or asymmetric 3-stage Clos networks under various routing strategies
(2004-04-10)
Chang, FH
;
Guo, JY
;
Hwang, FK
;
Lin, CK
;
應用數學系
Benes established the notion of wide-sense nonblocking by constructing an example on the symmetric 3-stage Clos network under packing which requires less hardware compared to strict nonblocking. This has remained the only example of a wide-sense non-blocking 3-stage Clos network which is not strictly nonblocking. In this paper, we study packing as well as several other routing strategies which have been studied in the literature and proved that no other example exists for the symmetric 3-stage Clos network. We then extend the study to asymmetric 3-stage Clos network for the first time. In particular, we extend Benes example to asymmetric 3-stage Clos network and show that these are the only two possible examples for the strategies under study. (C) 2003 Elsevier B.V. All rights reserved.