Goldberg, Robert R.; Shapiro, Jacob; Waxman, Jerry Optimal \(k\)-partitions. (English) Zbl 0905.90142 Congr. Numerantium 108, 17-32 (1995). 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 Keywords:set partition; optimal \(k\)-partition problem; polynomial algorithms; worst-case performance; best fit PDFBibTeX XMLCite \textit{R. R. Goldberg} et al., Congr. Numerantium 108, 17--32 (1995; Zbl 0905.90142)