A Greedy-heuristic for 3-partitioning with similar elements

H. Kellerer; G.J. Woeginger

doi:10.1007/BF02243817

A Greedy-heuristic for 3-partitioning with similar elements

H. Kellerer, G.J. Woeginger

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	271-278
Journal	Computing
Volume	50
Issue number	3
DOIs	https://doi.org/10.1007/BF02243817
Publication status	Published - 1993
Externally published	Yes

Access to Document

10.1007/BF02243817

Cite this

@article{fbb58d19fd0949b2b8e00df8482d9e93,

title = "A Greedy-heuristic for 3-partitioning with similar elements",

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.",

author = "H. Kellerer and G.J. Woeginger",

year = "1993",

doi = "10.1007/BF02243817",

language = "English",

volume = "50",

pages = "271--278",

journal = "Computing",

issn = "0010-485X",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - A Greedy-heuristic for 3-partitioning with similar elements

AU - Kellerer, H.

AU - Woeginger, G.J.

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

U2 - 10.1007/BF02243817

DO - 10.1007/BF02243817

M3 - Article

SN - 0010-485X

VL - 50

SP - 271

EP - 278

JO - Computing

JF - Computing

IS - 3

ER -

A Greedy-heuristic for 3-partitioning with similar elements

Abstract

Access to Document

Fingerprint

Cite this