| 2025 | ESA | A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs. | Mateusz Basiak, Marcin Bienkowski, Martin Bhm, Marek Chrobak, Lukasz Jez, Jir Sgall, Agnieszka Tatarczuk |
| 2024 | Algosensors | On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols. | Jordan Kuschner, Yugarshi Shashwat, Sarthak Yadav, Marek Chrobak |
| 2024 | ISAAC | Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths. | Sunny Atalig, Alexander Hickerson, Arrdya Srivastav, Tingting Zheng, Marek Chrobak |
| 2024 | ISAAC | On HTLC-Based Protocols for Multi-Party Cross-Chain Swaps. | Emily Clark, Chloe Georgiou, Katelyn Poon, Marek Chrobak |
| 2024 | TAMC | A Tight Threshold Bound for Search Trees with 2-Way Comparisons. | Sunny Atalig, Marek Chrobak |
| 2023 | STACS | Online Paging with Heterogeneous Cache Slots. | Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, Neal E. Young |
| 2023 | WADS | Classification via Two-Way Comparisons (Extended Abstract). | Marek Chrobak, Neal E. Young |
| 2023 | WALCOM | Better Hardness Results for the Minimum Spanning Tree Congestion Problem. | Huong Luu, Marek Chrobak |
| 2020 | WALCOM | A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips. | Miguel Coviello Gonzalez, Marek Chrobak |
| 2019 | CIAC | Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability (Extended Abstract). | Miguel Coviello Gonzalez, Marek Chrobak |
| 2019 | MFCS | Better Bounds for Online Line Chasing. | Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias |
| 2019 | SODA | A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines. | Pavel Vesel, Marek Chrobak, Lukasz Jez, Jir Sgall |
| 2016 | EDBT | Slowing the Firehose: Multi-Dimensional Diversity on Social Post Streams. | Shiwen Cheng, Marek Chrobak, Vagelis Hristidis |
| 2016 | ESA | Online Algorithms for Multi-Level Aggregation. | Marcin Bienkowski, Martin Bhm, Jaroslaw Byrka, Marek Chrobak, Christoph Drr, Luks Folwarczn, Lukasz Jez, Jiri Sgall, Kim Thang Nguyen, Pavel Vesel |
| 2016 | ISAAC | Online Packet Scheduling with Bounded Delay and Lookahead. | Martin Bhm, Marek Chrobak, Lukasz Jez, Fei Li, Jir Sgall, Pavel Vesel |
| 2016 | LATIN | Faster Information Gathering in Ad-Hoc Radio Tree Networks. | Marek Chrobak, Kevin P. Costello |
| 2015 | CIAC | Competitive Strategies for Online Clique Clustering. | Marek Chrobak, Christoph Drr, Bengt J. Nilsson |
| 2015 | CIAC | Scheduling with Gaps: New Models and Algorithms. | Marek Chrobak, Mordecai J. Golin, Tak Wah Lam, Dorian Nogneng |
| 2015 | ISAAC | Optimal Search Trees with 2-Way Comparisons. | Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young |
| 2015 | SOFSEM | Group Search on the Line. | Marek Chrobak, Leszek Gasieniec, Thomas Gorry, Russell Martin |
| 2014 | COCOA | Information Gathering in Ad-Hoc Radio Networks with Tree Topology. | Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, Darek Kowalski |
| 2014 | EDBT | Multi-Query Diversification in Microblogging Posts. | Shiwen Cheng, Anastasios Arvanitis, Marek Chrobak, Vagelis Hristidis |
| 2014 | SODA | Better Approximation Bounds for the Joint Replenishment Problem. | Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, Jir Sgall |
| 2014 | SPIRE | Sequence Decision Diagrams. | Hind Alhakami, Gianfranco Ciardo, Marek Chrobak |
| 2014 | WABI | An LP-Rounding Algorithm for Degenerate Primer Design. | Yu-Ting Huang, Marek Chrobak |
| 2013 | CIAC | A Greedy Approximation Algorithm for Minimum-Gap Scheduling. | Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor |
| 2013 | CIAC | LP-Rounding Algorithms for the Fault-Tolerant Facility Placement Problem. | Li Yan, Marek Chrobak |
| 2013 | FCT | Together or Separate? Algorithmic Aggregation Problems. | Marek Chrobak |
| 2013 | ICALP | Approximation Algorithms for the Joint Replenishment Problem with Deadlines. | Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young |
| 2013 | WADS | Online Control Message Aggregation in Chain Networks. | Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jir Sgall, Grzegorz Stachowiak |
| 2011 | ESA | Better Bounds for Incremental Frequency Allocation in Bipartite Graphs. | Marek Chrobak, Lukasz Jez, Jir Sgall |
| 2011 | ESA | Two-Bounded-Space Bin Packing Revisited. | Marek Chrobak, Jir Sgall, Gerhard J. Woeginger |
| 2010 | COCOON | Tile-Packing Tomography Is \mathbb | Marek Chrobak, Christoph Drr, Flavio Guiez, Antoni Lozano, Kim Thang Nguyen |
| 2010 | ESA | Caching Is Hard - Even in the Fault Model. | Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, Haifeng Xu |
| 2009 | AAIM | Algorithms for Placing Monitors in a Flow Network. | Francis Y. L. Chin, Marek Chrobak, Li Yan |
| 2009 | AAIM | Three Results on Frequency Assignment in Linear Cellular Networks. | Marek Chrobak, Jir Sgall |
| 2009 | SODA | Collecting weighted items from a dynamic queue. | Marcin Bienkowski, Marek Chrobak, Christoph Drr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak |
| 2008 | AAIM | Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems. | Marek Chrobak, Christoph Drr, Mathilde Hurand, Julien Robert |
| 2008 | INFOCOM | Policy-Aware Topologies for Efficient Inter-Domain Routing Evaluations. | Yihua He, Michalis Faloutsos, Srikanth V. Krishnamurthy, Marek Chrobak |
| 2008 | ISPASS | Dynamic Thermal Management through Task Scheduling. | Jun Yang, Xiuyi Zhou, Marek Chrobak, Youtao Zhang, Lingling Jin |
| 2008 | WAOA | Randomized Algorithms for Buffer Management with 2-Bounded Delay. | Marcin Bienkowski, Marek Chrobak, Lukasz Jez |
| 2008 | WAOA | Experimental Analysis of Scheduling Algorithms for Aggregated Links. | Wojciech Jawor, Marek Chrobak, Mart L. Molle |
| 2007 | APBC | Algorithmic Approaches to Selecting Control Clones in DNA Array Hybridization Experiments. | Qi Fu, Elizabeth Bent, James Borneman, Marek Chrobak, Neal E. Young |
| 2007 | ESA | Polynomial Time Algorithms for Minimum Energy Scheduling. | Philippe Baptiste, Marek Chrobak, Christoph Drr |
| 2007 | RTSS | Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines. | Marek Chrobak, Mathilde Hurand, Jir Sgall |
| 2007 | WAOA | Better Bounds for Incremental Medians. | Marek Chrobak, Mathilde Hurand |
| 2006 | LATIN | Oblivious Medians Via Online Bidding. | Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young |
| 2006 | LATIN | Competitive Analysis of Scheduling Algorithms for Aggregated Links. | Wojciech Jawor, Marek Chrobak, Christoph Drr |
| 2005 | COCOON | The Reverse Greedy Algorithm for the Metric | Marek Chrobak, Claire Kenyon, Neal E. Young |
| 2005 | Networking | Reducing Large Internet Topologies for Faster Simulations. | Vaishnavi Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Li Lao, Jun-Hong Cui, Allon G. Percus |
| 2004 | ESA | Improved Online Algorithms for Buffer Management in QoS Switches. | Marek Chrobak, Wojciech Jawor, Jir Sgall, Toms Tich |
| 2004 | ICALP | Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. | Marek Chrobak, Wojciech Jawor, Jir Sgall, Toms Tich |
| 2004 | SODA | The wake-up problem in multi-hop radio networks. | Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski |
| 2004 | STACS | Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. | Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jir Sgall, Toms Tich |
| 2004 | STACS | Errata to Analysis of the Harmonic Algorithm for Three Servers. | Marek Chrobak, Jir Sgall |
| 2003 | MFCS | Faster Algorithms for | Robert Benkoczi, Binay K. Bhattacharya, Marek Chrobak, Lawrence L. Larmore, Wojciech Rytter |
| 2003 | STACS | Analysis of the Harmonic Algorithm for Three Servers. | Marek Chrobak, Jir Sgall |
| 2002 | ICALP | Preemptive Scheduling in Overloaded Systems. | Marek Chrobak, Leah Epstein, John Noga, Jir Sgall, Rob van Stee, Toms Tich, Nodari Vakhania |
| 2001 | COCOON | A Randomized Algorithm for Gossiping in Radio Networks. | Marek Chrobak, Leszek Gasieniec, Wojciech Rytter |
| 2001 | ICALP | The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts. | Marek Chrobak, Jnos Csirik, Csand Imreh, John Noga, Jir Sgall, Gerhard J. Woeginger |
| 2001 | ISMB | Probe selection algorithms with applications in the analysis of microbial communities. | James Borneman, Marek Chrobak, Gianluca Della Vedova, Andres Figueroa, Tao Jiang |
| 2001 | MFCS | The k-Median Problem for Directed Trees. | Marek Chrobak, Lawrence L. Larmore, Wojciech Rytter |
| 2000 | FOCS | Fast Broadcasting and Gossiping in Radio Networks. | Marek Chrobak, Leszek Gasieniec, Wojciech Rytter |
| 2000 | STACS | The Weighted 2-Server Problem. | Marek Chrobak, Jir Sgall |
| 1999 | ESA | The 3-Server Problem in the Plane. | Wolfgang W. Bein, Marek Chrobak, Lawrence L. Larmore |
| 1998 | ESA | A Randomized Algorithm for Two Servers on the Line (Extended Abstract). | Yair Bartal, Marek Chrobak, Lawrence L. Larmore |
| 1998 | MFCS | Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms. | Marek Chrobak, Christoph Drr |
| 1998 | SODA | LRU is Better than FIFO. | Marek Chrobak, John Noga |
| 1998 | SODA | Competive Algorithms for Multilevel Caching and Relaxed List Update (Extended Abstract). | Marek Chrobak, John Noga |
| 1996 | ESA | Competive Analysis of Randomized Paging Algorithms. | Dimitris Achlioptas, Marek Chrobak, John Noga |
| 1994 | GD | Minimum-Width Grid Drawings of Plane Graphs. | Marek Chrobak, Shin-Ichi Nakano |
| 1993 | ISAAC | Page Migration Algorithms Using Work Functions. | Marek Chrobak, Lawrence L. Larmore, Nick Reingold, Jeffery R. Westbrook |
| 1992 | SODA | Generosity Helps, or an 11-Competitive Algorithm for Three Servers. | Marek Chrobak, Lawrence L. Larmore |
| 1991 | SODA | Efficient Sequential and Parallel Algorithms for Computing Recovery Points in Trees and Paths. | Marek Chrobak, David Eppstein, Giuseppe F. Italiano, Moti Yung |
| 1990 | MFCS | On Fast Algorithms for Two Servers. | Marek Chrobak, Lawrence L. Larmore |
| 1990 | SODA | New Results on Server Problems. | Marek Chrobak, Howard J. Karloff, T. H. Payne, Sundar Vishwanathan |
| 1989 | SPAA | An Efficient Parallel Algorithm for Computing a Large Independent Set in a Plan Graph. | Marek Chrobak, Joseph Naor |
| 1989 | WADS | Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw-Free Graphs. | Marek Chrobak, Joseph Naor, Mark B. Novick |
| 1987 | FCT | Saturating Flows in Networks. | Bogdan S. Chlebus, Marek Chrobak, Krzysztof Diks |
| 1987 | ICALP | Parallel 5-Colouring of Planar Graphs. | Torben Hagerup, Marek Chrobak, Krzysztof Diks |
| 1986 | FOCS | k+1 Heads Are Better than k for PDA's | Marek Chrobak, Ming Li |
| 1986 | MFCS | Unique Deciperability for Partially Commutative Alphabet (Extended Abstract). | Marek Chrobak, Wojciech Rytter |
| 1985 | ICALP | Hierarchies of One-Way Multihead Automata Languages. | Marek Chrobak |
| 1984 | MFCS | Nondeterminism Is Essential for Two-Way Counter Machines. | Marek Chrobak |