MCMarek Chrobak
Marek Chrobak
*This is an algorithmically generated author record based on publicly available information.
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
Research Interests
Marek Chrobak has a total of 99 co-authors. Here are the top co-authors by number of shared publications:
- Christoph Dürr
Sorbonne University
6 shared publications - Jiří Sgall
Computer Science Institute Faculty of Mathematics and Physics of Charles University Prague Czech Republic
6 shared publications - Neal E. Young
University of California
6 shared publications - Christoph Durr
Laboratoire de Recherche en Informatique Université Paris-Sud 91405 Orsay France
4 shared publications Christoph Dürr
CNRS, LIX UMR 7161, Ecole Polytechnique, Palaiseau, France
3 shared publications- Francis Sourd
Université Pierre et Marie Curie
3 shared publications
Latest Publications
- Open Access
- 29 May 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
We consider the classical single-source shortest path problem in directed weighted graphs. D. Eppstein proved recently an \(\Omega(n^{3})\) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this \(\Omega(n^{3})\) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm.- 29 May 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
Open AccessLower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
We consider the classical single-source shortest path problem in directed weighted graphs. D. Eppstein proved recently an \(\Omega(n^{3})\) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this \(\Omega(n^{3})\) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm. - Open Access
- 7 February 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (2) , 1-19
Classification via Two-Way Comparisons
Given a weighted, ordered query set \(Q\) and a partition of \(Q\) into classes, we study the problem of computing a minimum-cost decision tree that, given any query \(q\in Q\) , uses equality tests and less-than tests to determine \(q\) 's class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify \(q\) , not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes.- 7 February 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (2) , 1-19
Open AccessClassification via Two-Way Comparisons
Given a weighted, ordered query set \(Q\) and a partition of \(Q\) into classes, we study the problem of computing a minimum-cost decision tree that, given any query \(q\in Q\) , uses equality tests and less-than tests to determine \(q\) 's class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify \(q\) , not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes. - 27 December 2024
- Published by Springer Nature
- p. 106-116
On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
- 27 December 2024
- Published by Springer Nature
- p. 106-116
On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
- Open Access
- 17 October 2024
- Published by Springer Nature in Algorithmica
- Vol. 87 (1) , 89-131
Online Paging with Heterogeneous Cache Slots
It is natural to generalize the online $$k$$ -Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family $${\mathcal {S}}\subseteq 2^{[k]}$$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ ). As a function of $$|{\mathcal {S}}|$$ and k, the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ . For any laminar family $${\mathcal {S}}$$ of height h, the optimal ratios are O(hk) (deterministic) and $$O(h^2\log k)$$ (randomized). The special case of laminar $${\mathcal {S}}$$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $$\Theta (k)$$ . Offline All-or-One Paging is $$\mathbb{N}\mathbb{P}$$ -hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $$P$$ of pages, and is satisfied by fetching any page from $$P$$ into the cache. The optimal ratios for the latter problem (with laminar family of height h) are at most hk (deterministic) and $$hH_k$$ (randomized).- 17 October 2024
- Published by Springer Nature in Algorithmica
- Vol. 87 (1) , 89-131
Open AccessOnline Paging with Heterogeneous Cache Slots
It is natural to generalize the online $$k$$ -Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family $${\mathcal {S}}\subseteq 2^{[k]}$$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ ). As a function of $$|{\mathcal {S}}|$$ and k, the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ . For any laminar family $${\mathcal {S}}$$ of height h, the optimal ratios are O(hk) (deterministic) and $$O(h^2\log k)$$ (randomized). The special case of laminar $${\mathcal {S}}$$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $$\Theta (k)$$ . Offline All-or-One Paging is $$\mathbb{N}\mathbb{P}$$ -hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $$P$$ of pages, and is satisfied by fetching any page from $$P$$ into the cache. The optimal ratios for the latter problem (with laminar family of height h) are at most hk (deterministic) and $$hH_k$$ (randomized). - 3 May 2024
- Published by Springer Nature
- p. 99-110
A Tight Threshold Bound for Search Trees with 2-Way Comparisons
- 3 May 2024
- Published by Springer Nature
- p. 99-110
A Tight Threshold Bound for Search Trees with 2-Way Comparisons
- Open Access
A $φ$-Competitive Algorithm for Scheduling Packets with Deadlines
In the online packet scheduling problem with deadlines (PacketSchD, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets that are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketSchD, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a $\phi$-competitive online algorithm for PacketSchD (where $\phi\approx 1.618$ is the golden ratio), matching the previously established lower bound.Open AccessA $φ$-Competitive Algorithm for Scheduling Packets with Deadlines
In the online packet scheduling problem with deadlines (PacketSchD, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets that are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketSchD, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a $\phi$-competitive online algorithm for PacketSchD (where $\phi\approx 1.618$ is the golden ratio), matching the previously established lower bound. - 28 July 2023
- Published by Springer Nature
- p. 275-290
Classification via Two-Way Comparisons (Extended Abstract)
- 28 July 2023
- Published by Springer Nature
- p. 275-290
Classification via Two-Way Comparisons (Extended Abstract)
- Open Access
Online Paging with Heterogeneous Cache Slots
It is natural to generalize the online $k$-Server problem by allowing each request to specify not only a point $p$, but also a subset $S$ of servers that may serve it. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page $p$, but also a subset $S$ of cache slots, and is satisfied by having a copy of $p$ in some slot in $S$. We call this problem Slot-Heterogenous Paging. We parameterize the problem by specifying a family $\mathcal S \subseteq 2^{[k]}$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size $k$ and family $\mathcal S$: - If all request sets are allowed ($\mathcal S=2^{[k]}\setminus\{\emptyset\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard \Paging ($\mathcal S=\{[k]\}$). - As a function of $|\mathcal S|$ and $k$, the optimal deterministic ratio is polynomial: at most $O(k^2|\mathcal S|)$ and at least $\Omega(\sqrt{|\mathcal S|})$. - For any laminar family $\mathcal S$ of height $h$, the optimal ratios are $O(hk)$ (deterministic) and $O(h^2\log k)$ (randomized). - The special case of laminar $\mathcal S$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $\Theta(k)$. Offline All-or-One Paging is NP-hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $\mathcal P of pages, and is satisfied by fetching any page from $\mathcal P into the cache. The optimal ratios for the latter problem (with laminar family of height $h$) are at most $hk$ (deterministic) and $h\,H_k$ (randomized).Open AccessOnline Paging with Heterogeneous Cache Slots
It is natural to generalize the online $k$-Server problem by allowing each request to specify not only a point $p$, but also a subset $S$ of servers that may serve it. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page $p$, but also a subset $S$ of cache slots, and is satisfied by having a copy of $p$ in some slot in $S$. We call this problem Slot-Heterogenous Paging. We parameterize the problem by specifying a family $\mathcal S \subseteq 2^{[k]}$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size $k$ and family $\mathcal S$: - If all request sets are allowed ($\mathcal S=2^{[k]}\setminus\{\emptyset\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard \Paging ($\mathcal S=\{[k]\}$). - As a function of $|\mathcal S|$ and $k$, the optimal deterministic ratio is polynomial: at most $O(k^2|\mathcal S|)$ and at least $\Omega(\sqrt{|\mathcal S|})$. - For any laminar family $\mathcal S$ of height $h$, the optimal ratios are $O(hk)$ (deterministic) and $O(h^2\log k)$ (randomized). - The special case of laminar $\mathcal S$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $\Theta(k)$. Offline All-or-One Paging is NP-hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $\mathcal P of pages, and is satisfied by fetching any page from $\mathcal P into the cache. The optimal ratios for the latter problem (with laminar family of height $h$) are at most $hk$ (deterministic) and $h\,H_k$ (randomized). - Open Access
- 21 July 2021
- Published by Springer Nature in Journal of Scheduling
- Vol. 24 (4) , 381-403
Scheduling with gaps: new models and algorithms
- 21 July 2021
- Published by Springer Nature in Journal of Scheduling
- Vol. 24 (4) , 381-403
Open AccessScheduling with gaps: new models and algorithms
- 20 February 2020
- Published by Springer Nature
- p. 55-68
A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips
- 20 February 2020
- Published by Springer Nature
- p. 55-68
A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips