A TIGHT BOUND FOR 3-PARTITIONING

Let tau be a list of n items with nonnegative weights assigned to them . We want to assign these items to m bins (n less-than-or-equal-to 3m) with the object of minimizing the maximum weight of the bins such tha t no bin contains more than three items. As approximation algorithm fo r this NP-complete problem we use a modified version of the famous LPT -algorithm for multiprocessor scheduling. The main subject is to prove a worst-case bound of 4/3-1/3m.