Conference papers

  1. 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.
  2. 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).
  3. 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).
  4. 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
    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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. WALTZ: a strong Tzaar-playing program
    with Tomáš Valla.
    In Computer Games, CCIS 408, p. 81–96, Springer, 2014. View/hide summary.

Journal papers

  1. Relative Error Streaming Quantiles
    with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.
    Submitted. 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.
  2. A φ-Competitive Algorithm for Scheduling Packets with Deadlines
    with Marek Chrobak, Łukasz Jeż, Jiří Sgall.
    Submitted. ArXiv preprint. Slides for DIMAP seminar (longer). SODA slides (shorter). View/hide summary.
  3. 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).
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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. .
  12. 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.
  13. 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.
  14. 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.