Weighted flow time does not admit O(1)-competitive algorithms

N. Bansal, H.L. Chan

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    44 Citaten (Scopus)
    1 Downloads (Pure)

    Samenvatting

    We consider the classic online scheduling problem of minimizing the total weighted flow time on a single machine with preemptions. Here, each job j has an arbitrary arrival time rj, weight wj and size pj, and given a schedule its flow time is defined as the duration of time since its arrival until it completes its service requirement. The first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently, and it was widely believed that the problem admits a constant factor competitive algorithm. In this paper, we show an ¿(1) lower bound on the competitive ratio of any deterministic online algorithm. Our result is based on a gap amplification technique for online algorithms. Starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly.
    Originele taal-2Engels
    TitelProceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09, New York NY, USA, January 4-6, 2009)
    RedacteurenC. Mathieu
    Plaats van productieNew York
    UitgeverijAssociation for Computing Machinery, Inc
    Pagina's1238-1244
    DOI's
    StatusGepubliceerd - 2009

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Weighted flow time does not admit O(1)-competitive algorithms'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit