Browsing by Author "Onn, S"

Now showing 1 - 4 of 4

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.
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.