### Abstract

Let t be a list of n items with nonnegative weights assigned to them. We want to assign these items to m bins (n = 3m) with the object of minimizing the maximum weight of the bins such that no bin contains more than three items. As approximation algorithm for 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/3 m.

Original language | English |
---|---|

Pages (from-to) | 249-259 |

Journal | Discrete Applied Mathematics |

Volume | 45 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1993 |

## Fingerprint Dive into the research topics of 'A tight bound for 3-partitioning'. Together they form a unique fingerprint.

## Cite this

Kellerer, H., & Woeginger, G. J. (1993). A tight bound for 3-partitioning.

*Discrete Applied Mathematics*,*45*(3), 249-259. https://doi.org/10.1016/0166-218X(93)90013-E