ISSN:
1436-5057
Keywords:
90B35
;
68M20
;
k-partitioning containing kernels
;
NP-complete
;
worst case analysis
;
LPT-algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Seik≥2 eine natürliche Zahl undG= $$\{ g_1 ,g_2 , \cdots ,g_m \} \cup \{ t_1 ,t_2 , \cdots ,t_n \} $$ eine Menge von höchstenskm nichtnegativen ganzen Zahlen. Gesucht ist eine Partition vonG= $$\{ g_1 ,g_2 , \cdots ,g_m \} \cup \{ t_1 ,t_2 , \cdots ,t_n \} $$ inm Teilmengen, die jeweils nicht mehr alsk Elemente enthalten, sodaß alleg i (Kerne genannt) unterschiedlichen Teilmengen zugeordnet werden und die maximale Summe von Zahlen in einer dieser Teilmengen möglichst klein wird. Wir zeigen zunächst, daß für jedesk≥3 dieses Problem NP-vollständig im starken Sinne ist. Als Heuristik für dieses Problem benutzen wir eine revidierte Version des bekannten LPT-Algorithmus für das Multiprozessorscheduling-Problem. Fürk=3 zeigen wir eine Worst-Case Schranke von 3/2–1/2m.
Notes:
Abstract LetG= $$\{ g_1 ,g_2 , \cdots ,g_m \} \cup \{ t_1 ,t_2 , \cdots ,t_n \} $$ be a list of items with nonnegative weights assigned andk≥2 be an integer. The objective is to find an assignment of the items to the bins such that allg i (called kernels) are assigned to different bins, such that no bin contains more thank 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 anyk≥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 fork=3.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02247409
Permalink
