On minimizing the total flow time on multiple machines

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    1 Citation (Scopus)

    Abstract

    We consider the problem of minimizing the total flow time on multiple machines with preemption, where the flow time of a job is the time spent since it arrives until it finishes. Our main result is a quasi-polynomial time approximation scheme for a constant number of machines (m). The result also extends to total weighted flow time where either the job weights or the job sizes are polynomially bounded by the number of jobs (n). We also show that the dependence on m cannot be substantially improved. In particular, obtaining an O(1) approximation for the weighted case (even when all weights and sizes are polynomially bounded by n) by an algorithm with running time npolylog(n,m) would imply that NP ¿ DTIME(npolylog(n)).
    Original languageEnglish
    Title of host publicationProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04, New Orleans LA, USA, January 11-14, 2004)
    EditorsJ.I. Munri
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    Pages572-574
    ISBN (Print)0-89871-558-X
    Publication statusPublished - 2004

    Fingerprint Dive into the research topics of 'On minimizing the total flow time on multiple machines'. Together they form a unique fingerprint.

    Cite this