×

Optimal \(k\)-partitions. (English) Zbl 0905.90142

Summary: This paper considers the optimal \(k\)-partition problem, a generalization of the classical set partition problem. The optimal \(k\)-partition problem arises in many application domains such as load balancing and multiple stage processing. Since this problem is NP-hard, we discuss some polynomial algorithms which provide approximations to ideal solutions and compare the experimental results of several algorithms for random data. In addition, the worst-case performance of the best fit algorithm for the case \(k= 2\) is analyzed and an upper bound of the error produced by the algorithm is computed.

MSC:

90C27 Combinatorial optimization
05A18 Partitions of sets
PDFBibTeX XMLCite