標題: Sphere-separable partitions of multi-parameter elements
作者: Golanya, Boaz
Hwang, Frank K.
Rothbluma, Uriel G.
應用數學系
Department of Applied Mathematics
關鍵字: partitions;combinatorial optimization;separation;polynomial bounds
公開日期: 15-Mar-2008
摘要: We show the optimality of sphere-separable partitions for problems where n vectors in d-dimensional space are to be partitioned into p categories to minimize a cost function which is dependent in the sum of the vectors in each category; the sum of the squares of their Euclidean norms; and the number of elements in each category. We further show that the number of these partitions is polynomial in n. These results broaden the class of partition problems for which an optimal solution is guaranteed within a prescribed set whose size is polynormially bounded in n. Applications of the results are demonstrated through examples. (C) 2007 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.dam.2006.06.012
http://hdl.handle.net/11536/9570
ISSN: 0166-218X
DOI: 10.1016/j.dam.2006.06.012
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 156
Issue: 6
起始頁: 838
結束頁: 845
Appears in Collections:Articles


Files in This Item:

  1. 000254482400003.pdf