Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Weighted Flow Time does not Admit O(1)-competitive Algorithms

Bansal, N., & Chan, H.-L. (2009). Weighted Flow Time does not Admit O(1)-competitive Algorithms. In C. Mathieu (Ed.), Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1238-1244). New York, NY: ACM. doi:10.1137/1.9781611973068.134.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-18ED-8 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-3BF3-6
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bansal, Nikhil1, Autor
Chan, Ho-Leung2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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 $r_j$, weight $w_j$ and size $p_j$, 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 $\omega(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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2009-03-2120092009
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518336
DOI: 10.1137/1.9781611973068.134
Anderer: Local-ID: C1256428004B93B8-DF4FDF682F979567C125754D00374F2C-Chan2008
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms
Veranstaltungsort: New York, NY, USA
Start-/Enddatum: 2009-01-04 - 2009-01-06

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms
  Kurztitel : SODA 2009
Genre der Quelle: Konferenzband
 Urheber:
Mathieu, Claire1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: New York, NY : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 1238 - 1244 Identifikator: -