Martin Böhm
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Martin Böhm has a total of 36 co-authors. Here are the top co-authors by number of shared publications:
- Pavel Veselý
Charles University
16 shared publications - Jiří Sgall
Computer Science Institute Faculty of Mathematics and Physics of Charles University Prague Czech Republic
14 shared publications - Łukasz Jeż
Institute of Computer Science University of Wroc law Poland
7 shared publications - Marcin Bienkowski
University of Wroclaw, Wroclaw, Poland
4 shared publications - Rob van Stee
Department of Computer Science, University of Leicester, Leicester, UK
3 shared publications - Fei Li
Department of Computer Science, George Mason University, Fairfax, VA 22030, USA
2 shared publications
Latest Publications
- 13 October 2022
- Published by Elsevier in Theoretical Computer Science
- Vol. 938, 1-15
Discovering and certifying lower bounds for the online bin stretching problem
- 13 October 2022
- Published by Elsevier in Theoretical Computer Science
- Vol. 938, 1-15
Discovering and certifying lower bounds for the online bin stretching problem
- 28 June 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (5) , 463-469
Throughput scheduling with equal additive laxity
- 28 June 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (5) , 463-469
Throughput scheduling with equal additive laxity
- 1 March 2021
- Published by Elsevier in Theoretical Computer Science
- Vol. 861, 133-143
New results on multi-level aggregation
- 1 March 2021
- Published by Elsevier in Theoretical Computer Science
- Vol. 861, 133-143
New results on multi-level aggregation
- 1 January 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 68 (1) , 214-232
Online Algorithms for Multilevel Aggregation
Online Algorithms for Hierarchical Aggregation Problems Data and inventory aggregation problems arise in multicasting, sensor networks, communication in organization hierarchies, and in supply chain management. These problems are naturally online, in the sense that aggregation decisions need to be made without information about future requests. We study these problems with a general tree structure of links that can be used for deliveries. This generalizes some well-studied optimization problems: trees of depth one capture the TCP acknowledgment problem, and trees of depth two capture the joint replenishment problem. For trees of depth one and two, constant-competitive online algorithms are known. We solve a major open problem by giving a constant-competitive algorithm for trees of arbitrary (fixed) depth. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.
- 1 January 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 68 (1) , 214-232
Online Algorithms for Multilevel Aggregation
Online Algorithms for Hierarchical Aggregation Problems Data and inventory aggregation problems arise in multicasting, sensor networks, communication in organization hierarchies, and in supply chain management. These problems are naturally online, in the sense that aggregation decisions need to be made without information about future requests. We study these problems with a general tree structure of links that can be used for deliveries. This generalizes some well-studied optimization problems: trees of depth one capture the TCP acknowledgment problem, and trees of depth two capture the joint replenishment problem. For trees of depth one and two, constant-competitive online algorithms are known. We solve a major open problem by giving a constant-competitive algorithm for trees of arbitrary (fixed) depth. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.
- 20 December 2019
- Published by Springer Nature in Algorithmica
- Vol. 82 (6) , 1640-1653
Nested Convex Bodies are Chaseable
- 20 December 2019
- Published by Springer Nature in Algorithmica
- Vol. 82 (6) , 1640-1653
Nested Convex Bodies are Chaseable
- 1 July 2019
- Published by Elsevier in Theoretical Computer Science
- Vol. 776, 95-113
Online packet scheduling with bounded delay and lookahead
- 1 July 2019
- Published by Elsevier in Theoretical Computer Science
- Vol. 776, 95-113
Online packet scheduling with bounded delay and lookahead
- Open Access
- 4 February 2019
- Published by Springer Nature in Annals of Operations Research
- Vol. 298 (1-2) , 7-42
On packet scheduling with adversarial jamming and speedup
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 $$\phi +1\approx 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).- 4 February 2019
- Published by Springer Nature in Annals of Operations Research
- Vol. 298 (1-2) , 7-42
Open AccessOn packet scheduling with adversarial jamming and speedup
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 $$\phi +1\approx 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). - Open Access
On Packet Scheduling with Adversarial Jamming and Speedup
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 properties 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 $\phi+1\approx 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. and the lower bound by Anta et al.Open AccessOn Packet Scheduling with Adversarial Jamming and Speedup
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 properties 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 $\phi+1\approx 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. and the lower bound by Anta et al.