The Library
Almost tight bounds for reordering buffer management
Tools
Tools
Tools
Adamaszek, Anna, Czumaj, Artur, Englert, Matthias and Räcke, Harald (2011) Almost tight bounds for reordering buffer management. In: STOC'11 Symposium on Theory of Computing Conference (Co-located with FCRC 2011), San Jose, CA, USA, 6-8 Jun 2011. Published in: STOC '11 Proceedings of the 43rd annual ACM symposium on Theory of computing pp. 607-616. doi:10.1145/1993636.1993717 ISSN 9781450306911.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1145/1993636.1993717
Abstract
We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first non-trivial lower bounds for this problem by showing that deterministic online algorithms have a competitive ratio of at least Ω(√{log k/log log k}) and randomized online algorithms have a competitive ratio of at least Ω(log log k), where k denotes the size of the buffer.
We complement this by presenting a deterministic online algorithm for the reordering buffer management problem that obtains a competitive ratio of O(√log k), almost matching the lower bound. This improves upon an algorithm by Avigdor-Elgrabli and Rabani (SODA 2010) that achieves a competitive ratio of O(log k/ log log k).
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | STOC '11 Proceedings of the 43rd annual ACM symposium on Theory of computing | ||||
| Publisher: | ACM | ||||
| ISSN: | 9781450306911 | ||||
| Book Title: | Proceedings of the 43rd annual ACM symposium on Theory of computing - STOC '11 | ||||
| Official Date: | 2011 | ||||
| Dates: |
|
||||
| Page Range: | pp. 607-616 | ||||
| DOI: | 10.1145/1993636.1993717 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | STOC'11 Symposium on Theory of Computing Conference (Co-located with FCRC 2011) | ||||
| Type of Event: | Conference | ||||
| Location of Event: | San Jose, CA, USA | ||||
| Date(s) of Event: | 6-8 Jun 2011 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
