Output details
11 - Computer Science and Informatics
University of Warwick
Output title
Almost tight bounds for reordering buffer management
Type
E - Conference contribution
Name of conference/published proceedings
STOC '11 Proceedings of the 43rd annual ACM symposium on Theory of computing
Volume number
-
Issue number
-
First page of article
607
ISSN of proceedings
-
Year of publication
2011
Number of additional authors
3
Additional information
<12> Presented at one of the two strongest conferences in theoretical computer science, this paper provides a near-complete characterisation of the performance of online algorithms for the reordering buffer management problem, one of the most fundamental problems in the area of online algorithms. This research has been instrumental to further advances in this area by Avigdor-Elgrabli and Rabani (Hebrew University), presented at FOCS’13, who match some of the paper’s lower bounds, and by Im (Duke) and Moseley (TTI Chicago), to be presented at SODA’14, who extend some bounds for the weighted version of the problem and in the off-line case.
Interdisciplinary
-
Cross-referral requested
-
Research group
T - Theory and Foundations
Citation count
2
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
