### Abstract

For a given list of 3m items with positive lengths we look for a partition intom subsets containing 3 elements each, such that the ratio of the largest sum of lengths to the smallest sum of lengths is as small as possible. Let ρG be the value of this ratio using a Greedy-heuristic and ρ* the optimal value of this ratio; furthermore let β be the ratio of the largest length of an item to the smallest length. Then we will show that for 1≤β≤4 the inequality ρG/ρ*≤(4β+7)(2β+5) holds and this bound is tight.

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

Pages (from-to) | 271-278 |

Journal | Computing |

Volume | 50 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1993 |

Externally published | Yes |

## Fingerprint Dive into the research topics of 'A Greedy-heuristic for 3-partitioning with similar elements'. Together they form a unique fingerprint.

## Cite this

Kellerer, H., & Woeginger, G. J. (1993). A Greedy-heuristic for 3-partitioning with similar elements.

*Computing*,*50*(3), 271-278. https://doi.org/10.1007/BF02243817