.png){kind=icon}
.png){kind=icon}
Return
Three-partitioning containing kernels: Complexity and heuristic
.png){kind=icon}
PRE
AI
DOI：10.1007/BF02247409.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Let G = {g(1), g(2) ,..., gm}U{t(1), t(2) ,..., t(n)} be a list of items with nonnegative weights assigned and k greater than or equal to 2 be an integer. The objective is to find an assignment of the items to the bins such that all g(i) (called kernels) are assigned to different bins, such that no bin contains more than k items, and such that the maximum weight assigned to any bin becomes minimum. In this paper, we first prove that the problem is NP-complete in the strong sense for any k greater than or equal to 3. As heuristic for this problem, we use a modified version of the famous LPT-algorithm for multiprocessor scheduling, and we show a worst case bound of 3/2 - 1/2m for k = 3.
Keywords:
k-partitioning containing kernels
NP-complete
worst case analysis
LPT-algorithm