Three-partitioning containing kernels: Complexity and heuristic

S. -P. Chen

doi:10.1007/BF02247409

1996-09-01

PRE

DOI：10.1007/BF02247409

原文链接

原文求助

摘要

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.

Keyword:

k-partitioning containing kernels

NP-complete

worst case analysis

LPT-algorithm