Browsing by Author "Rothblum, UG"

Now showing 1 - 10 of 10

A polynomial time algorithm for shaped partition problems
(1999-11-29)
Hwang, FK
;
Onn, S
;
Rothblum, UG
;
應用數學系
;
Department of Applied Mathematics
We consider the class of shaped partition problems of partitioning n given vectors in d-dimensional criteria space into p parts so as to maximize an arbitrary objective function which is convex on the sum of vectors in each part, subject to arbitrary constraints on the number of elements in each part. This class has broad expressive power and captures NP-hard problems even if either d or p is fixed. In contrast, we show that when both d and p are fixed, the problem can be solved in strongly polynomial time. Our solution method relies on studying the corresponding class of shaped partition polytopes. Such polytopes may have exponentially many vertices and facets even when one of d or p is fixed; however, we show that when both d and p are fixed, the number of vertices of any shaped partition polytope is O(n(d(p2))) and all vertices can be produced in strongly polynomial time.
Explicit solution of partitioning problems over a 1-dimensional parameter space
(2000-09-01)
Hwang, FK
;
Onn, S
;
Rothblum, UG
;
應用數學系
;
Department of Applied Mathematics
We consider a class of partitioning problems where the partitioned set is a finite set of real numbers and the objective function of a partition is a function of the vector whose coordinates are the sums of the elements in each part of the given partition (the number of such parts is assumed given). We obtain an explicit solution of such partitioning problem with polynomial complexity bounds. (C) 2000 John Wiley & Sons, Inc.
Linear-shaped partition problems
(2000-05-01)
Hwang, FK
;
Onn, S
;
Rothblum, UG
;
應用數學系
;
Department of Applied Mathematics
We establish the polynomial-time solvability of a class of vector partition problems with linear objectives subject to restrictions on the number of elements in each part. (C) 2000 Published by Elsevier Science B.V. All rights reserved.
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.
Partition polytopes over 1-dimensional points
(1999-06-01)
Gao, B
;
Hwang, FK
;
Li, WCW
;
Rothblum, UG
;
應用數學系
We consider partitions of a finite set whose elements are associated with a single numerical attribute. For each partition we consider the vector obtained by taking the sums of the attributes corresponding to the elements in the parts (sets) of the partition, and we study the convex hulls of sets of such vectors. For sets of all partitions with prescribed number of elements in each set, we obtain a characterizing system of linear inequalities and an isomorphic representation of the face lattice. The relationship of the resulting class of polytopes to that of generalized permutahedra is explored.
Partition-optimization with Schur convex sum objective functions
(2005)
Hwang, FK
;
Rothblum, UG
;
應用數學系
;
Department of Applied Mathematics
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 θ(π) = (&USigma;(i&ISIN;π 1) θ(i),..., &USigma;(i&ISIN;π 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.
Permutation polytopes corresponding to strongly supermodular functions
(2004-08-15)
Hwang, FK
;
Lee, JS
;
Rothblum, UG
;
應用數學系
;
Department of Applied Mathematics
Throughout, let p be a positive integer and let Sigma be the set of permutations over {1,....p}. A real-valued function lambda over subsets of {1,... p}, with lambda(theta)=0, defines a mapping of Sigma into R-p where delta is an element of Sigma is mapped into the vector lambda(delta) whose kth coordinate (lambda(delta))(k) is the augmented-value obtained from adding k to the coordinates that precede it, according to the ranking induced by sigma. The permutation polytope corresponding to is then the convex hull of the vectors corresponding to all permutations. We introduce a new class of strongly supermodular functions and for such functions we derive an isomorphic representation for the face-lattices of the corresponding permutation polytope. (C) 2003 Elsevier B.V. All rights reserved.
Representations and characterizations of vertices of bounded-shape partition polytopes
(1998-07-15)
Hwang, FK
;
Onn, S
;
Rothblum, UG
;
應用數學系
;
Department of Applied Mathematics
Consider a finite set whose elements are associated with vectors of common dimension. A partition of such a set is associated with a matrix whose columns are the sums of the vectors corresponding to each part. The partition polytope associated with a class of partitions (that share the number of parts) is then the convex hull of the corresponding matrices. We derive representations and characterizations of these polytopes and their vertices, (C) 1998 Elsevier Science Inc, All rights reserved.
Sortabilities of partition properties
(1999)
Chang, GJ
;
Chen, FL
;
Huang, LL
;
Hwang, FK
;
Nuan, ST
Consider the partition of a set of integers into parts. Various partition properties have been proposed in the literature to facilitate the restriction of the focus of attention to some small class of partitions. Recently, Hwang, Rothblum and Yao defined and studied the sortability of these partition properties as a tool to prove the existence of a partition with such a property in a given family. In this paper we determine the sortability indices of the seven most interesting properties of partitions providing a complete solution to the sortability issue.
Sortability of vector partitions
(2003-02-28)
Hwang, FK
;
Lee, JS
;
Liu, YC
;
Rothblum, UG
;
應用數學系
Some combinatorial properties of partitioning points in R-1 have recently been well studied. We extend this study to points in R-d with the hope to benefit clustering and optimal partition problems in R-d. (C) 2002 Elsevier Science B.V. All rights reserved.