**Fully Scalable MPC Algorithms for Clustering in High Dimension**

with Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, and Robert Krauthgamer.

To appear in ICALP 2024. ArXiv preprint.**Approximation Guarantees for Shortest Superstrings: Simpler and Better**

with Matthias Englert and Nicolaos Matsakis.

In ISAAC 2023. Preprint.**Streaming Facility Location in High Dimension via Geometric Hashing**

with Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Mingwei Yang.

In FOCS 2022, p. 450-461, IEEE. doi:10.1109/FOCS54457.2022.00050. ArXiv preprint. Slides for FOCS.**Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios**

with Matthias Englert and Nicolaos Matsakis.

In STOC 2022, p. 317-330, ACM, 2022. doi:10.1145/3519935.3520001. ArXiv preprint.**Streaming Algorithms for Geometric Steiner Forest**

with Artur Czumaj, Shaofeng H.-C. Jiang, and Robert Krauthgamer.

In ICALP 2022, p. 47:1--47:20. LIPIcs link. ArXiv preprint.**Improved Analysis of Online Balanced Clustering**

with Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, and Jiří Sgall.

In WAOA 2021, LNCS 12982, p. 224-233, Springer, 2022.

doi:10.1007/978-3-030-92702-8_14. ArXiv preprint.**Theory meets Practice at the Median: a worst case comparison of relative error quantile algorithms**

with Graham Cormode, Abhinav Mishra, and Joseph Ross.

In KDD 2021 (Applied Data Science Track), p. 2722–2731. doi:10.1145/3447548.3467152. ArXiv preprint. Video (by Joe).**Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop**

with Antonios Antoniadis, Matthias Englert, and Nicolaos Matsakis.

In ICALP 2021. LIPIcs link. ArXiv preprint. Video for ICALP (25 min).**Relative Error Streaming Quantiles**

with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.

In PODS 2021, p. 96-108. doi:10.1145/3452021.3458323.

**Best Paper**(proof)**Invited to JACM**

**2022 ACM SIGMOD Research Highlight Award**

ArXiv preprint.

Proof-of-concept Python code. Much better implementation in Java, C++, and Python in Apache DataSketches library.

Video for PODS 2021. Video for WOLA 2020 (longer). WOLA slides.**A Tight Lower Bound for Comparison-Based Quantile Summaries**

with Graham Cormode.

In PODS 2020, p. 81-93, ACM, 2020, doi:10.1145/3375395.3387650. ArXiv preprint. BCTCS slides. Video record from PODS (starts at 29:00). View/hide summary.**Streaming Algorithms for Bin Packing and Vector Scheduling**

with Graham Cormode.

In WAOA 2019, LNCS 11926, p. 72-88, Springer, 2020. ArXiv preprint. View/hide summary. WAOA slides.**A φ-Competitive Algorithm for Scheduling Packets with Deadlines**

with Marek Chrobak, Łukasz Jeż, Jiří Sgall.

In SODA 2019, p. 123-142, Society for Industrial and Applied Mathematics, 2019. doi:10.1137/1.9781611975482.9

ArXiv preprint. Slides for DIMAP seminar (longer). SODA slides (shorter). View/hide summary.**Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices**

with Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, and Tomáš Toufar.

In STACS 2018, LIPIcs, p. 26:1--26:15, Schloss Dagstuhl, 2018. LIPIcs link. ArXiv preprint. View/hide summary.**On Packet Scheduling with Adversarial Jamming and Speedup**

with Martin Böhm, Łukasz Jeż, Jiří Sgall.

In WAOA 2017, LNCS 10787, p. 190-206, Springer, 2018. ArXiv preprint. WAOA slides. View/hide summary.**Online Chromatic Number is PSPACE-Complete**

with Martin Böhm.

In IWOCA 2016, LNCS 9843, p. 16-28, Springer, 2016.

**Best Student Paper**ArXiv preprint. HALG 2017 poster. View/hide summary.**Online Packet Scheduling with Bounded Delay and Lookahead**

with Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall.

In ISAAC 2016, LIPIcs, p. 21:1--21:13, Schloss Dagstuhl, 2016. LIPIcs link, ArXiv preprint. MAPSP slides. View/hide summary.**Online Algorithms for Multi-Level Aggregation.**

with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang.

In ESA 2016, Leibniz International Proceedings in Informatics (LIPIcs), p. 12:1-12:17, Schloss Dagstuhl, 2016. LIPIcs link, ArXiv preprint. View/hide summary.**Better algorithms for online bin stretching**

with Martin Böhm, Jiří Sgall, Rob van Stee.

In WAOA 2014, LNCS 8952, p. 236-247, Springer, 2015. ArXiv preprint. View/hide summary.**Online colored bin packing**

with Martin Böhm, Jiří Sgall.

In WAOA 2014, LNCS 8952, p. 35-46, Springer, 2015. ArXiv preprint. View/hide summary.**WALTZ: a strong Tzaar-playing program**

with Tomáš Valla.

In Computer Games, CCIS 408, p. 81–96, Springer, 2014. View/hide summary.

**Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios**

with Matthias Englert and Nicolaos Matsakis.

Submitted. ArXiv preprint.**Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop**

with Antonios Antoniadis, Matthias Englert, and Nicolaos Matsakis.

Submitted. ArXiv preprint. Video for ICALP (25 min).**Streaming Algorithms for Geometric Steiner Forest**

with Artur Czumaj, Shaofeng H.-C. Jiang, and Robert Krauthgamer.

ACM Transactions on Algorithms doi:10.1145/3663666. ArXiv preprint.**Relative Error Streaming Quantiles**[Extended Abstract]

with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.

ACM SIGMOD Record, vol. 51(1), p. 69–76, 2022. doi:10.1145/3542700.3542717.

**2022 ACM SIGMOD Research Highlight Award**SIGMOD Record link.

Nice 1-page technical perspective by Rasmus Pagh.

(This is an 8-page abstract of the main paper.)**Relative Error Streaming Quantiles**

with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.

Journal of the ACM doi:10.1145/3617891. ArXiv preprint.**A φ-Competitive Algorithm for Scheduling Packets with Deadlines**

with Marek Chrobak, Łukasz Jeż, Jiří Sgall.

SIAM J. Comput., vol. 51(5), p. 1626–1691, 2022.

DOI: 10.1137/21M1469753. ArXiv preprint.

Slides for DIMAP seminar (longer). SODA slides (shorter). View/hide summary.**Packet Scheduling: Plans, Monotonicity, and the Golden Ratio**

ACM SIGACT News, vol. 52(2), p. 72–84, 2021.

DOI: 10.1145/3471469.3471481 Preprint.

A column summarizing the ideas behind the φ-competitive algorithm for packet scheduling (SODA '19).**Streaming Algorithms for Bin Packing and Vector Scheduling**

with Graham Cormode.

Theory of Computing Systems, vol. 65, p. 916-942, 2021.

DOI: 10.1007/s00224-020-10011-y ArXiv preprint. View/hide summary.**New Results on Multi-Level Aggregation**

with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang.

Theoretical Computer Science, vol. 861, p. 133-143, 2021.

DOI: 10.1016/j.tcs.2021.02.016 View/hide summary.**Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices.**

with Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, and Tomáš Toufar.

SIAM J. Discrete Math., vol. 35(1), p. 546–574, 2021.

doi:10.1137/18M1209489. ArXiv preprint. View/hide summary.**On Packet Scheduling with Adversarial Jamming and Speedup**

with Martin Böhm, Łukasz Jeż, Jiří Sgall.

Annals of Operations Research, vol. 298, p. 7–42, 2021.

doi:10.1007/s10479-019-03153-x. ArXiv preprint. WAOA slides. View/hide summary.**Online Packet Scheduling with Bounded Delay and Lookahead**

with Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall.

Theoretical Computer Science, vol. 776, p. 95-113, 2019.

doi:10.1016/j.tcs.2019.01.013. ArXiv preprint. MAPSP slides. View/hide summary.**Online Chromatic Number is PSPACE-Complete**

with Martin Böhm.

Theory of Computing Systems, vol. 62(6), p. 1366–1391, Springer, 2018.

doi:10.1007/s00224-017-9797-2. ArXiv preprint. HALG 2017 poster View/hide summary.**Logarithmic price of buffer downscaling on line metrics**

with Marcin Bienkowski, Martin Bohm, Łukasz Jeż, Paweł Laskoś-Grabowski, Jan Marcinkowski, Jiří Sgall, Aleksandra Spyra.

Theoretical Computer Science, vol. 707, p. 89-93, Elsevier, 2018, doi:10.1016/j.tcs.2017.10.008. ArXiv preprint. View/hide summary.**Online Algorithms for Multi-Level Aggregation**

with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang.

Operations Research, vol. 68(1), p. 214-232, 2020.

doi:10.1287/opre.2019.1847. ArXiv preprint. View/hide summary. .**A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5**

with Martin Böhm, Jiří Sgall, Rob van Stee.

Journal of Combinatorial Optimization, vol. 34(3), p. 810-828, Springer, 2017.

doi:10.1007/s10878-017-0114-4. ArXiv preprint. View/hide summary.**Online Bin Stretching with Three Bins**

with Martin Böhm, Jiří Sgall, Rob van Stee.

Journal of Scheduling, vol. 20(6), p. 601-621, Springer, 2017, doi:10.1007/s10951-016-0504-y. ArXiv preprint. View/hide summary.**Colored Bin Packing: Online Algorithms and Lower Bounds**

with Martin Böhm, György Dósa, Leah Epstein, Jiří Sgall.

Algorithmica, vol. 80(1), p. 155-184, Springer, 2018.

doi:10.1007/s00453-016-0248-2. View/hide summary.