The Library
Approximation algorithms for time-constrained scheduling on line networks
Tools
Räcke, Harald and Rosen, Adi (2009) Approximation algorithms for time-constrained scheduling on line networks. In: 21st ACM Symposium on Parallelism in Algorithms and Architectures, Calgary, Canada, August 11-13, 2009. Published in: SPAA '09: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architecture pp. 337-346. ISBN 978-1-60558-606-9. doi:10.1145/1583991.1584071
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/1583991.1584071
Abstract
We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is to maximize the number of packets that arrive to their destinations by their respective deadlines, given the network constraints.
We consider the line network, and a setting where each node has a buffer of size B packets (where B can be finite or infinite), and each edge has capacity C >= 1. To the best of our knowledge this is the first work to study time-constrained scheduling in a setting when buffers can be of limited size. We give approximation algorithms that achieve (expected) approximation ratio of O(max{log* n - log* B, 1} + max{log* Sigma - log* C, 1}), where n is the length of the line, and E is the maximum slack a message can have (the slack is the number of time steps a message can be idle and still arrive within its deadline).
A special case of our setting is the setting of buffers of unlimited capacity and edge capacities 1, which has been previously studied by Adler et al. [2]. For this case our results considerably improve upon previous results: Via a slight modification of our algorithms we also obtain an approximation ratio of O(min{log* n, log* Sigma, log* M}) (where M is the number of messages in the instance), which is a significant improvement upon the results of Adler et al.
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: | SPAA '09: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architecture | ||||
Publisher: | Association for Computing Machinery, Inc. | ||||
ISBN: | 978-1-60558-606-9 | ||||
Official Date: | 2009 | ||||
Dates: |
|
||||
Number of Pages: | 10 | ||||
Page Range: | pp. 337-346 | ||||
DOI: | 10.1145/1583991.1584071 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 21st ACM Symposium on Parallelism in Algorithms and Architectures | ||||
Type of Event: | Conference | ||||
Location of Event: | Calgary, Canada | ||||
Date(s) of Event: | August 11-13, 2009 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |