A performance guarantee for the greedy set-partitioning algorithm (Q790814)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A performance guarantee for the greedy set-partitioning algorithm
scientific article

    Statements

    A performance guarantee for the greedy set-partitioning algorithm (English)
    0 references
    1984
    0 references
    Let S be a set of positive numbers and m an integer not less than 2. The problem is to partition S into m subsets such that the ratio of the largest set to the smallest set is as small as possible. Let \(\rho_ g(S)\) be the value of this ratio using the greedy or largest-first rule and \(\rho_ 0(S)\) be the smallest possible value of this ratio, i.e., the optimal value. The authors prove that \(\rho_ g(S)/\rho_ 0(S)\leq 7/5,\) and that this is a best possible bound for all m.
    0 references
    set-partitioning
    0 references
    subsets
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references