The Library
On packet scheduling with adversarial jamming and speedup
Tools
Tools
Tools
Böhm, Martin, Jeż, Łukasz, Sgall, Jiří and Veselý, Pavel (2021) On packet scheduling with adversarial jamming and speedup. Annals of Operations Research , 298 . pp. 7-42. doi:10.1007/s10479-019-03153-x ISSN 0254-5330.
|
PDF
WRAP-packet-scheduling-adversarial-jamming-speedup-Vesely-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (807Kb) | Preview |
|
![[img]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
dcs-270319-wrap--jam-journal.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (831Kb) |
Official URL: http://dx.doi.org/10.1007/s10479-019-03153-x
Abstract
In Packet Scheduling with Adversarial Jamming, packets of arbitrary sizes arrive over time to be transmitted over a channel in which instantaneous jamming errors occur at times chosen by the adversary and not known to the algorithm. The transmission taking place at the time of jamming is corrupt, and the algorithm learns this fact immediately. An online algorithm maximizes the total size of packets it successfully transmits and the goal is to develop an algorithm with the lowest possible asymptotic competitive ratio, where the additive constant may depend on packet sizes. Our main contribution is a universal algorithm that works for any speedup and packet sizes and, unlike previous algorithms for the problem, it does not need to know these parameters in advance. We show that this algorithm guarantees 1-competitiveness with speedup 4, making it the first known algorithm to maintain 1-competitiveness with a moderate speedup in the general setting of arbitrary packet sizes. We also prove a lower bound of ϕ+1≈2.618 on the speedup of any 1-competitive deterministic algorithm, showing that our algorithm is close to the optimum. Additionally, we formulate a general framework for analyzing our algorithm locally and use it to show upper bounds on its competitive ratio for speedups in [1, 4) and for several special cases, recovering some previously known results, each of which had a dedicated proof. In particular, our algorithm is 3-competitive without speedup, matching both the (worst-case) performance of the algorithm by Jurdzinski et al. (Proceedings of the 12th workshop on approximation and online algorithms (WAOA), LNCS 8952, pp 193–206, 2015. http://doi.org/10.1007/978-3-319-18263-6_17) and the lower bound by Anta et al. (J Sched 19(2):135–152, 2016. http://doi.org/10.1007/s10951-015-0451-z).
| Item Type: | Journal Article | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) | |||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Online algorithms, Computer scheduling | |||||||||||||||
| Journal or Publication Title: | Annals of Operations Research | |||||||||||||||
| Publisher: | Springer New York LLC | |||||||||||||||
| ISSN: | 0254-5330 | |||||||||||||||
| Official Date: | March 2021 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Volume: | 298 | |||||||||||||||
| Page Range: | pp. 7-42 | |||||||||||||||
| DOI: | 10.1007/s10479-019-03153-x | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
| Date of first compliant deposit: | 28 March 2019 | |||||||||||||||
| Date of first compliant Open Access: | 28 March 2019 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
