The Library
Reordering buffers with logarithmic diameter dependency for trees
Tools
Englert, Matthias and Räcke, Harald (2017) Reordering buffers with logarithmic diameter dependency for trees. In: 28th ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017. Published in: SODA '17 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms 1224-1234 . ISBN 9781611974782. doi:10.1137/1.9781611974782.79
|
PDF
WRAP-reodering-buffers-logarithmic-dependency-Englert-2017.pdf - Published Version - Requires a PDF viewer. Download (732Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611974782.79
Abstract
In the reordering buffer problem a sequence of items located in a metric space arrive online, and have to be processed by a single server moving within the metric space. At any point in time, the first k still unprocessed items from the sequence are available for processing and the server has to select one of these items and process it by visiting its location. The goal is to process all items while minimizing the total distance the server moves. Englert, R¨acke, Westermann (STOC’07) gave a deterministic O(D · log k)-competitive online algorithm for weighted tree metrics with hop-diameter D. We improve the analysis of this algorithm and significantly improve the dependency on D. Specifically, we show that the algorithm is in fact O(log D+log k)-competitive. Our analysis is quite robust. Even when an optimal algorithm, to which we compare the online algorithm, is allowed to choose between the first h > k unprocessed items, the online algorithm is still O(h·(log D+log h)/k)- competitive. For h = (1 + ε) · k, with constant ε > 0, this is optimal. Our results also imply better competitive ratio for general metric spaces, improving the randomized O(log n · log2 k) result for n-point metric spaces from STOC’07 to O(log n · 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 | ||||||
Library of Congress Subject Headings (LCSH): | Algorithms, Logarithms, Metric spaces | ||||||
Journal or Publication Title: | SODA '17 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||
Publisher: | SIAM ; ACM | ||||||
ISBN: | 9781611974782 | ||||||
Official Date: | 16 January 2017 | ||||||
Dates: |
|
||||||
Page Range: | 1224-1234 | ||||||
DOI: | 10.1137/1.9781611974782.79 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Date of first compliant deposit: | 16 December 2016 | ||||||
Date of first compliant Open Access: | 20 June 2017 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 28th ACM-SIAM Symposium on Discrete Algorithms | ||||||
Type of Event: | Other | ||||||
Location of Event: | Barcelona, Spain | ||||||
Date(s) of Event: | 16-19 Jan 2017 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year