A Greedy-heuristic for 3-partitioning with similar elements

H. Kellerer, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

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 languageEnglish
Pages (from-to)271-278
JournalComputing
Volume50
Issue number3
DOIs
Publication statusPublished - 1993
Externally publishedYes

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

  • Cite this