A tight bound for 3-partitioning

H. Kellerer, G.J. Woeginger

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    16 Citaten (Scopus)
    1 Downloads (Pure)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)249-259
    TijdschriftDiscrete Applied Mathematics
    Nummer van het tijdschrift3
    StatusGepubliceerd - 1993


    Duik in de onderzoeksthema's van 'A tight bound for 3-partitioning'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit