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.

Full text not available from this repository.

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 > 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
Date:	2011
Page Range:	pp. 607-616
Identification Number:	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
URI:	http://wrap.warwick.ac.uk/id/eprint/42239

Request changes to a record

Actions (login required)

View Item