Minimizing weighted flow time

N. Bansal, K. Dhamdhere

    Research output: Contribution to journalArticleAcademicpeer-review

    26 Citations (Scopus)

    Abstract

    We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O(k)-competitive for k weight classes. This implies an O(log W)-competitive algorithm, where W is the maximum to minimum ratio of weights. This algorithm also implies an O(log n + log P)-approximation ratio for the problem, where P is the ratio of the maximum to minimum job size and n is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a (1 + ϵ)-speed, (1 +1/ϵ)-competitive online algorithm.
    Original languageEnglish
    Article number39
    Pages (from-to)39-1/14
    Number of pages14
    JournalACM Transactions on Algorithms
    Volume3
    Issue number4
    DOIs
    Publication statusPublished - 2007

    Fingerprint Dive into the research topics of 'Minimizing weighted flow time'. Together they form a unique fingerprint.

    Cite this