{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T05:20:44Z","timestamp":1761110444544,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T00:00:00Z","timestamp":1549238400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T00:00:00Z","timestamp":1549238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Polish National Science Center","award":["2016\/21\/D\/ST6\/02402"],"award-info":[{"award-number":["2016\/21\/D\/ST6\/02402"]}]},{"name":"Grantov\u00e1 Agentura \u00c8esk\u00e9 Republiky","award":["17-09142S"],"award-info":[{"award-number":["17-09142S"]}]},{"name":"Grantov\u00e1 Agentura, Univerzita Karlova","award":["634217"],"award-info":[{"award-number":["634217"]}]},{"name":"Polish National Science Center","award":["2016\/22\/E\/ST6\/00499"],"award-info":[{"award-number":["2016\/22\/E\/ST6\/00499"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\phi +1\\approx 2.618$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03d5<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:mn>2.618<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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,\u00a04) 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\u00a0et al.\u00a0(Proceedings of the 12th workshop on approximation and online algorithms (WAOA), LNCS 8952, pp 193\u2013206, 2015. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/doi.org\/10.1007\/978-3-319-18263-6_17\">http:\/\/doi.org\/10.1007\/978-3-319-18263-6_17<\/jats:ext-link>) and the lower bound by Anta\u00a0et al.\u00a0(J Sched 19(2):135\u2013152, 2016. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/doi.org\/10.1007\/s10951-015-0451-z\">http:\/\/doi.org\/10.1007\/s10951-015-0451-z<\/jats:ext-link>).<\/jats:p>","DOI":"10.1007\/s10479-019-03153-x","type":"journal-article","created":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T14:56:46Z","timestamp":1549292206000},"page":"7-42","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On packet scheduling with adversarial jamming and speedup"],"prefix":"10.1007","volume":"298","author":[{"given":"Martin","family":"B\u00f6hm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0141ukasz","family":"Je\u017c","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1169-7934","authenticated-orcid":false,"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,2,4]]},"reference":[{"key":"3153_CR1","doi-asserted-by":"crossref","unstructured":"Anta, A. F., Georgiou, C., Kowalski, D. R., Widmer, J., & Zavou, E. (2016). Measuring the impact of adversarial errors on packet scheduling strategies. Journal of Scheduling, 19(2), 135\u2013152. Also appeared in Proceedings of SIROCCO 2013 (pp. 261\u2013273). http:\/\/doi.org\/10.1007\/s10951-015-0451-z.","DOI":"10.1007\/s10951-015-0451-z"},{"key":"3153_CR2","doi-asserted-by":"crossref","unstructured":"Anta, A. F., Georgiou, C., Kowalski, D. R., & Zavou, E. (2015). Online parallel scheduling of non-uniform tasks: Trading failures for energy. Theoretical Computer Science, 590, 129\u2013146. Also appeared in Proceedings of FCT 2013 (pp. 145\u2013158). http:\/\/doi.org\/10.1016\/j.tcs.2015.01.027.","DOI":"10.1016\/j.tcs.2015.01.027"},{"key":"3153_CR3","doi-asserted-by":"crossref","unstructured":"Anta, A. F., Georgiou, C., Kowalski, D. R., & Zavou, E. (2018). Competitive analysis of fundamental scheduling algorithms on a fault-prone machine and the impact of resource augmentation. Future Generation Computer Systems, 78, 245\u2013256. Also appeared in Proceedings of the 2nd international workshop on adaptive resource management and scheduling for cloud computing (ARMS-CC@PODC 2015), LNCS 9438 (pp. 1\u201316). http:\/\/doi.org\/10.1016\/j.future.2016.05.042.","DOI":"10.1016\/j.future.2016.05.042"},{"issue":"1","key":"3153_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A., Karp, R. M., Tardos, G., & Wigderson, A. (1994). On the power of randomization in on-line algorithms. Algorithmica, 11(1), 2\u201314. https:\/\/doi.org\/10.1007\/BF01294260.","journal-title":"Algorithmica"},{"key":"3153_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6hm, M., Je\u017c, \u0141., Sgall, J., & Vesel\u00fd, P. (2018). On packet scheduling with adversarial jamming and speedup. In Proceedings of the 15th international workshop on approximation and online algorithms (WAOA) (pp. 190\u2013206). http:\/\/doi.org\/10.1007\/978-3-319-89441-6_15.","DOI":"10.1007\/978-3-319-89441-6_15"},{"key":"3153_CR6","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., & El-Yaniv, R. (1998). Online computation and competitive analysis. Cambridge: Cambridge University Press."},{"key":"3153_CR7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0022-0000(03)00070-9","volume":"67","author":"M Chrobak","year":"2003","unstructured":"Chrobak, M., Epstein, L., Noga, J., Sgall, J., van Stee, R., Tich\u00fd, T., et al. (2003). Preemptive scheduling in overloaded systems. Journal of Computer and System Sciences, 67, 183\u2013197. https:\/\/doi.org\/10.1016\/S0022-0000(03)00070-9.","journal-title":"Journal of Computer and System Sciences"},{"key":"3153_CR8","doi-asserted-by":"crossref","unstructured":"Garncarek, P., Jurdzi\u0144ski, T., & Lory\u015b, K. (2017). Fault-tolerant online packet scheduling on parallel channels. In 2017 IEEE international parallel and distributed processing symposium (IPDPS) (pp. 347\u2013356). http:\/\/doi.org\/10.1109\/IPDPS.2017.105.","DOI":"10.1109\/IPDPS.2017.105"},{"key":"3153_CR9","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jpdc.2015.07.007","volume":"84","author":"C Georgiou","year":"2015","unstructured":"Georgiou, C., & Kowalski, D. R. (2015). On the competitiveness of scheduling dynamically injected tasks on processes prone to crashes and restarts. Journal of Parallel and Distributed Computing, 84, 94\u2013107. https:\/\/doi.org\/10.1016\/j.jpdc.2015.07.007.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"9","key":"3153_CR10","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell Labs Technical Journal, 45(9), 1563\u20131581.","journal-title":"Bell Labs Technical Journal"},{"key":"3153_CR11","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Kowalski, D. R., & Lory\u015b, K. (2015). Online packet scheduling under adversarial jamming. In Proceedings of the 12th workshop on approximation and online algorithms (WAOA), LNCS 8952 (pp. 193\u2013206). See http:\/\/arxiv.org\/abs\/1310.4935 for missing proofs. http:\/\/doi.org\/10.1007\/978-3-319-18263-6_17.","DOI":"10.1007\/978-3-319-18263-6_17"},{"key":"3153_CR12","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., & Pruhs, K. (2000). Speed is as powerful as clairvoyance. Journal of the ACM, 47(4), 617\u2013643. Also appeared in Proceedings of the 36nd IEEE symposium on foundations of computer science (FOCS) (pp. 214\u2013221) (1995). http:\/\/doi.org\/10.1145\/347476.347479.","DOI":"10.1145\/347476.347479"},{"issue":"1\u20134","key":"3153_CR13","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D. (1988). Competitive snoopy caching. Algorithmica, 3(1\u20134), 79\u2013119.","journal-title":"Algorithmica"},{"key":"3153_CR14","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/j.jalgor.2003.10.004","volume":"52","author":"TW Lam","year":"2004","unstructured":"Lam, T. W., Ngan, T.-W., & To, K.-K. (2004). Performance guarantee for EDF under overload. Journal of Algorithms, 52, 193\u2013206. https:\/\/doi.org\/10.1016\/j.jalgor.2003.10.004.","journal-title":"Journal of Algorithms"},{"key":"3153_CR15","unstructured":"Lam, T. W., & To, K.-K. (1999). Trade-offs between speed and processor in hard-deadline scheduling. In Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 623\u2013632). ACM\/SIAM. http:\/\/dl.acm.org\/citation.cfm?id=314500.314884."},{"key":"3153_CR16","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00453-001-0068-9","volume":"32","author":"CA Phillips","year":"2002","unstructured":"Phillips, C. A., Stein, C., Torng, E., & Wein, J. (2002). Optimal time-critical scheduling via resource augmentation. Algorithmica, 32, 163\u2013200. https:\/\/doi.org\/10.1007\/s00453-001-0068-9.","journal-title":"Algorithmica"},{"issue":"4","key":"3153_CR17","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/1243401.1243411","volume":"34","author":"K Pruhs","year":"2007","unstructured":"Pruhs, K. (2007). Competitive online scheduling for server systems. SIGMETRICS Performance Evaluation Review, 34(4), 52\u201358. https:\/\/doi.org\/10.1145\/1243401.1243411.","journal-title":"SIGMETRICS Performance Evaluation Review"},{"key":"3153_CR18","unstructured":"Schewior, K. (2016). Deadline scheduling and convex-body chasing. PhD dissertation, TU Berlin. http:\/\/doi.org\/10.14279\/depositonce-5427."},{"issue":"2","key":"3153_CR19","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D. D., & Tarjan, R. E. (1985). Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2), 202\u2013208. https:\/\/doi.org\/10.1145\/2786.2793.","journal-title":"Communications of the ACM"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-019-03153-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03153-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03153-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,13]],"date-time":"2021-02-13T20:42:02Z","timestamp":1613248922000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-019-03153-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,4]]},"references-count":19,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["3153"],"URL":"https:\/\/doi.org\/10.1007\/s10479-019-03153-x","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2019,2,4]]},"assertion":[{"value":"4 February 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}