Marek Chrobak

269 papers A* 17A 17B 33C 13Misc 3Journal 169Unranked 12
YearRankTypeTitle / Venue / Authors
2026 J jnl
Two Complexity Results on Spanning-Tree Congestion Problems.
CoRR
Sunny Atalig, Marek Chrobak, Christoph Dürr, Petr Kolman, Huong Luu, Jirí Sgall, Gregory Zhu
2025 A conf
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs.
ESA
Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Lukasz Jez, Jirí Sgall, Agnieszka Tatarczuk
2025 J jnl
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs.
CoRR
Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Lukasz Jez, Jirí Sgall, Agnieszka Tatarczuk
2025 J jnl
A Refutation of Elmasry's O(m √n)-Time Algorithm for Single-Source Shortest Paths.
CoRR
Sunny Atalig, Marek Chrobak
2025 J jnl
A note on local convergence of iterative processes for pipe network analysis.
Comput. Appl. Math.
Huong Luu, Marek Chrobak
2025 J jnl
A tight threshold bound for search trees with 2-way comparisons.
Theor. Comput. Sci.
Sunny Atalig, Marek Chrobak
2025 J jnl
Better Hardness Results for the Minimum Spanning Tree Congestion Problem.
Algorithmica
Huong Luu, Marek Chrobak
2025 J jnl
Classification via Two-Way Comparisons.
ACM Trans. Algorithms
Marek Chrobak, Neal E. Young
2025 J jnl
Online Paging with Heterogeneous Cache Slots.
Algorithmica
Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, Neal E. Young
2024 C conf
A Tight Threshold Bound for Search Trees with 2-Way Comparisons.
TAMC
Sunny Atalig, Marek Chrobak
2024 B conf
Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths.
ISAAC
Sunny Atalig, Alexander Hickerson, Arrdya Srivastav, Tingting Zheng, Marek Chrobak
2024 J jnl
Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths.
CoRR
Sunny Atalig, Alexander Hickerson, Arrdya Srivastav, Tingting Zheng, Marek Chrobak
2024 B conf
On HTLC-Based Protocols for Multi-Party Cross-Chain Swaps.
ISAAC
Emily Clark, Chloe Georgiou, Katelyn Poon, Marek Chrobak
2024 J jnl
On HTLC-Based Protocols for Multi-Party Cross-Chain Swaps.
CoRR
Emily Clark, Chloe Georgiou, Katelyn Poon, Marek Chrobak
2024 — conf
On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols.
ALGOWIN
Jordan Kuschner, Yugarshi Shashwat, Sarthak Yadav, Marek Chrobak
2024 J jnl
On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols.
CoRR
Jordan Kuschner, Yugarshi Shashwat, Sarthak Yadav, Marek Chrobak
2023 J jnl
A Note on Local Convergence of Iterative Processes for Pipe Network Analysis.
CoRR
Huong Luu, Marek Chrobak
2023 J jnl
A Tight Threshold Bound for Search Trees with 2-way Comparisons.
CoRR
Sunny Atalig, Marek Chrobak
2023 B conf
Better Hardness Results for the Minimum Spanning Tree Congestion Problem.
WALCOM
Huong Luu, Marek Chrobak
2023 B conf
Classification via Two-Way Comparisons (Extended Abstract).
WADS
Marek Chrobak, Neal E. Young
2023 J jnl
Classification via two-way comparisons.
CoRR
Marek Chrobak, Neal E. Young
2023 A conf
Cross-Chain Swaps with Preferences.
CSF
Eric Chan, Marek Chrobak, Mohsen Lesani
2023 A conf
Online Paging with Heterogeneous Cache Slots.
STACS
Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, Neal E. Young
2023 J jnl
Structural Properties of Search Trees with 2-way Comparisons.
CoRR
Sunny Atalig, Marek Chrobak, Erfan Mousavian, Jiri Sgall, Pavel Veselý
2022 J jnl
A Simple Algorithm for Optimal Search Trees with Two-way Comparisons.
ACM Trans. Algorithms
Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young
2022 J jnl
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines.
SIAM J. Comput.
Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall
2022 J jnl
Better Hardness Results for the Minimum Spanning Tree Congestion Problem.
CoRR
Huong Luu, Marek Chrobak
2022 J jnl
Cross-chain Swaps with Preferences.
CoRR
Eric Chan, Marek Chrobak, Mohsen Lesani
2022 J jnl
On Huang and Wong's algorithm for generalized binary split trees.
Acta Informatica
Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young
2022 J jnl
Online Paging with Heterogeneous Cache Slots.
CoRR
Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, Neal E. Young
2021 J jnl
A Simple Algorithm for Optimal Search Trees with Two-Way Comparisons.
CoRR
Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young
2021 J jnl
Information gathering in ad-hoc radio networks.
Inf. Comput.
Marek Chrobak, Kevin P. Costello, Leszek Gasieniec
2021 J jnl
New results on multi-level aggregation.
Theor. Comput. Sci.
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukás Folwarczný, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý
2021 J jnl
On the Cost of Unsuccessful Searches in Search Trees with Two-way Comparisons.
CoRR
Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young
2021 J jnl
On the cost of unsuccessful searches in search trees with two-way comparisons.
Inf. Comput.
Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young
2021 J jnl
Scheduling with gaps: new models and algorithms.
J. Sched.
Marek Chrobak, Mordecai J. Golin, Tak Wah Lam, Dorian Nogneng
2020 B conf
A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips.
WALCOM
Miguel Coviello Gonzalez, Marek Chrobak
2020 J jnl
A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips.
ACM J. Exp. Algorithmics
Miguel Coviello Gonzalez, Marek Chrobak
2020 J jnl
Algorithmic approaches to selecting control clones in DNA array hybridization experiments.
CoRR
Qi Fu, Elizabeth Bent, James Borneman, Marek Chrobak, Neal E. Young
2020 — conf
Modeling Fluid Mixing in Microfluidic Grids.
CSC
Huong Luu, Marek Chrobak
2020 J jnl
Online Algorithms for Multilevel Aggregation.
Oper. Res.
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukás Folwarczný, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý
2020 J jnl
Online Clique Clustering.
Algorithmica
Marek Chrobak, Christoph Dürr, Aleksander Fabijan, Bengt J. Nilsson
2020 J jnl
Towards a theory of mixing graphs: A characterization of perfect mixability.
Theor. Comput. Sci.
Miguel Coviello Gonzalez, Marek Chrobak
2019 J jnl
A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips.
CoRR
Miguel Coviello Gonzalez, Marek Chrobak
2019 A* conf
A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines.
SODA
Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall
2019 J jnl
An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs.
CoRR
Alexander Choi, Marek Chrobak, Kevin P. Costello
2019 B conf
Better Bounds for Online Line Chasing.
MFCS
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias
2019 J jnl
Information Gathering in Ad-Hoc Radio Networks.
CoRR
Marek Chrobak, Kevin P. Costello, Leszek Gasieniec
2019 J jnl
Modeling Fluid Mixing in Microfluidic Grids.
CoRR
Huong Luu, Marek Chrobak
2019 J jnl
On Huang and Wong's Algorithm for Generalized Binary Split Trees.
CoRR
Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young
2019 J jnl
Online packet scheduling with bounded delay and lookahead.
Theor. Comput. Sci.
Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý
2019 C conf
Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability (Extended Abstract).
CIAC
Miguel Coviello Gonzalez, Marek Chrobak
2018 J jnl
A φ-Competitive Algorithm for Scheduling Packets with Deadlines.
CoRR
Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall
2018 J jnl
Better Bounds for Online Line Chasing.
CoRR
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias
2018 J jnl
Faster Information Gathering in Ad-Hoc Radio Tree Networks.
Algorithmica
Marek Chrobak, Kevin P. Costello
2018 J jnl
Information gathering in ad-hoc radio networks with tree topology.
Inf. Comput.
Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, Dariusz R. Kowalski
2018 J jnl
Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability.
CoRR
Miguel Coviello Gonzalez, Marek Chrobak
2017 J jnl
A greedy approximation algorithm for minimum-gap scheduling.
J. Sched.
Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor
2017 C ed.
Algorithms for Sensor Systems - 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2016, Aarhus, Denmark, August 25-26, 2016, Revised Selected Papers
ALGOSENSORS
Marek Chrobak, Antonio Fernández Anta, Leszek Gasieniec, Ralf Klasing
2016 — ch.
Algorithm DC-Tree for k-Servers on Trees.
Encyclopedia of Algorithms
Marek Chrobak
2016 B conf
Faster Information Gathering in Ad-Hoc Radio Tree Networks.
LATIN
Marek Chrobak, Kevin P. Costello
2016 A conf
Online Algorithms for Multi-Level Aggregation.
ESA
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukás Folwarczný, Lukasz Jez, Jiri Sgall, Kim Thang Nguyen, Pavel Veselý
2016 B conf
Online Packet Scheduling with Bounded Delay and Lookahead.
ISAAC
Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý
2016 J jnl
Online Packet Scheduling with Bounded Delay and Lookahead.
CoRR
Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý
2016 B conf
Slowing the Firehose: Multi-Dimensional Diversity on Social Post Streams.
EDBT
Shiwen Cheng, Marek Chrobak, Vagelis Hristidis
2016 — ch.
Work-Function Algorithm for k-Servers.
Encyclopedia of Algorithms
Marek Chrobak
2015 J jnl
A note on NP-hardness of preemptive mean flow-time scheduling for parallel machines.
J. Sched.
Odile Bellenguez-Morineau, Marek Chrobak, Christoph Dürr, Damien Prot
2015 J jnl
Approximation algorithms for the joint replenishment problem with deadlines.
J. Sched.
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young
2015 C conf
Competitive Strategies for Online Clique Clustering.
CIAC
Marek Chrobak, Christoph Dürr, Bengt J. Nilsson
2015 J jnl
Faster Information Gathering in Ad-Hoc Radio Tree Networks.
CoRR
Marek Chrobak, Kevin P. Costello
2015 B conf
Group Search on the Line.
SOFSEM
Marek Chrobak, Leszek Gasieniec, Thomas Gorry, Russell Martin
2015 J jnl
LP-rounding algorithms for the fault-tolerant facility placement problem.
J. Discrete Algorithms
Li Yan, Marek Chrobak
2015 J jnl
Online Algorithms for Multi-Level Aggregation.
CoRR
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukás Folwarczný, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý
2015 B conf
Optimal Search Trees with 2-Way Comparisons.
ISAAC
Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young
2015 J jnl
Optimal search trees with equality tests.
CoRR
Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young
2015 C conf
Scheduling with Gaps: New Models and Algorithms.
CIAC
Marek Chrobak, Mordecai J. Golin, Tak Wah Lam, Dorian Nogneng
2014 J jnl
A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines.
CoRR
Odile Bellenguez-Morineau, Marek Chrobak, Christoph Dürr, Damien Prot
2014 J jnl
Algorithms for Placing Monitors in a Flow Network.
Algorithmica
Francis Y. L. Chin, Marek Chrobak, Li Yan
2014 C conf
An LP-Rounding Algorithm for Degenerate Primer Design.
WABI
Yu-Ting Huang, Marek Chrobak
2014 J jnl
Approximation Algorithms for Clique Clustering.
CoRR
Marek Chrobak, Christoph Dürr, Bengt J. Nilsson
2014 A* conf
Better Approximation Bounds for the Joint Replenishment Problem.
SODA
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, Jirí Sgall
2014 C conf
Information Gathering in Ad-Hoc Radio Networks with Tree Topology.
COCOA
Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, Darek Kowalski
2014 J jnl
Information Gathering in Ad-Hoc Radio Networks with Tree Topology.
CoRR
Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, Dariusz R. Kowalski
2014 B conf
Multi-Query Diversification in Microblogging Posts.
EDBT
Shiwen Cheng, Anastasios Arvanitis, Marek Chrobak, Vagelis Hristidis
2014 J jnl
Online aggregation problems.
SIGACT News
Marek Chrobak
2014 J jnl
PRISE2: Software for designing sequence-selective PCR primers and probes.
BMC Bioinform.
Yu-Ting Huang, Jiue-in Yang, Marek Chrobak, James Borneman
2014 J jnl
Scheduling with Gaps: New Models and Algorithms.
CoRR
Marek Chrobak, Mordecai J. Golin, Tak Wah Lam, Dorian Nogneng
2014 C conf
Sequence Decision Diagrams.
SPIRE
Hind Alhakami, Gianfranco Ciardo, Marek Chrobak
2013 J jnl
A
Theor. Comput. Sci.
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak
2013 C conf
A Greedy Approximation Algorithm for Minimum-Gap Scheduling.
CIAC
Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor
2013 — conf
Approximation Algorithms for the Joint Replenishment Problem with Deadlines.
ICALP (1)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young
2013 J jnl
Better Approximation Bounds for the Joint Replenishment Problem.
CoRR
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall
2013 J jnl
Better bounds for incremental frequency allocation in bipartite graphs.
Theor. Comput. Sci.
Marek Chrobak, Lukasz Jez, Jirí Sgall
2013 J jnl
Collecting Weighted Items from a Dynamic Queue.
Algorithmica
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak
2013 C conf
LP-Rounding Algorithms for the Fault-Tolerant Facility Placement Problem.
CIAC
Li Yan, Marek Chrobak
2013 B conf
Online Control Message Aggregation in Chain Networks.
WADS
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall, Grzegorz Stachowiak
2013 B conf
Together or Separate? Algorithmic Aggregation Problems.
FCT
Marek Chrobak
2012 — ch.
Algorithmic Aspects of Energy-Efficient Computing.
Handbook of Energy-Aware and Green Computing
Marek Chrobak
2012 J jnl
Approximation Algorithms for the Joint Replenishment Problem with Deadlines
CoRR
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak
2012 J jnl
Caching Is Hard - Even in the Fault Model.
Algorithmica
Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, Haifeng Xu
2012 J jnl
LP-rounding Algorithms for the Fault-Tolerant Facility Placement Problem
CoRR
Li Yan, Marek Chrobak
2012 J jnl
Obtaining Provably Legitimate Internet Topologies.
IEEE/ACM Trans. Netw.
Yihua He, Michalis Faloutsos, Srikanth V. Krishnamurthy, Marek Chrobak
2012 J jnl
Polynomial-time algorithms for minimum energy scheduling.
ACM Trans. Algorithms
Philippe Baptiste, Marek Chrobak, Christoph Dürr
2012 J jnl
Tile-Packing Tomography Is NP-hard.
Algorithmica
Marek Chrobak, Christoph Dürr, Flavio Guiñez, Antoni Lozano, Kim Thang Nguyen
2011 J jnl
Algorithms for temperature-aware task scheduling in microprocessor systems.
Sustain. Comput. Informatics Syst.
Marek Chrobak, Christoph Dürr, Mathilde Hurand, Julien Robert
2011 J jnl
Approximation algorithms for the Fault-Tolerant Facility Placement problem.
Inf. Process. Lett.
Li Yan, Marek Chrobak
2011 J jnl
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs
CoRR
Marek Chrobak, Lukasz Jez, Jirí Sgall
2011 A conf
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs.
ESA
Marek Chrobak, Lukasz Jez, Jirí Sgall
2011 J jnl
Better bounds for incremental medians.
Theor. Comput. Sci.
Marek Chrobak, Mathilde Hurand
2011 J jnl
New Results on the Fault-Tolerant Facility Placement Problem
CoRR
Li Yan, Marek Chrobak
2011 J jnl
Randomized competitive algorithms for online buffer management in the adaptive adversary model.
Theor. Comput. Sci.
Marcin Bienkowski, Marek Chrobak, Lukasz Jez
2011 J jnl
SIGACT news online algorithms column 19.
SIGACT News
Marek Chrobak
2011 A conf
Two-Bounded-Space Bin Packing Revisited.
ESA
Marek Chrobak, Jirí Sgall, Gerhard J. Woeginger
2010 J jnl
A low-cost memory remapping scheme for address bus protection.
J. Parallel Distributed Comput.
Jun Yang, Lan Gao, Youtao Zhang, Marek Chrobak, Hsien-Hsin S. Lee
2010 — conf
Caching Is Hard - Even in the Fault Model.
ESA (1)
Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, Haifeng Xu
2010 J jnl
Performance-aware thermal management via task scheduling.
ACM Trans. Archit. Code Optim.
Xiuyi Zhou, Jun Yang, Marek Chrobak, Youtao Zhang
2010 — conf
Polynomial Time Algorithms for Minimum Energy Scheduling.
Scheduling
Marek Chrobak, Philippe Baptiste, Christoph Dürr
2010 J jnl
SIGACT news online algorithms column 16.
SIGACT News
Marek Chrobak
2010 J jnl
SIGACT news online algorithms column 17.
SIGACT News
Marek Chrobak
2010 J jnl
Three results on frequency assignment in linear cellular networks.
Theor. Comput. Sci.
Marek Chrobak, Jirí Sgall
2010 Misc conf
Tile-Packing Tomography Is \mathbb
COCOON
Marek Chrobak, Christoph Dürr, Flavio Guiñez, Antoni Lozano, Kim Thang Nguyen
2009 J jnl
Algorithms for Placing Monitors in a Flow Network
CoRR
Francis Y. L. Chin, Marek Chrobak, Li Yan
2009 C conf
Algorithms for Placing Monitors in a Flow Network.
AAIM
Francis Y. L. Chin, Marek Chrobak, Li Yan
2009 J jnl
Algorithms for testing fault-tolerance of sequenced jobs.
J. Sched.
Marek Chrobak, Mathilde Hurand, Jirí Sgall
2009 A* conf
Collecting weighted items from a dynamic queue.
SODA
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak
2009 J jnl
Introduction to the SIGACT news online algorithms column.
SIGACT News
Marek Chrobak
2009 J jnl
Polynomial Time Algorithms for Minimum Energy Scheduling
CoRR
Philippe Baptiste, Marek Chrobak, Christoph Dürr
2009 J jnl
SIGACT news online algorithms column 14.
SIGACT News
Marek Chrobak
2009 C conf
Three Results on Frequency Assignment in Linear Cellular Networks.
AAIM
Marek Chrobak, Jirí Sgall
2009 J jnl
Tile Packing Tomography is NP-hard
CoRR
Marek Chrobak, Christoph Dürr, Flavio Guiñez, Antoni Lozano, Kim Thang Nguyen
2008 — ch.
Algorithm DC-Tree for kServers on Trees.
Encyclopedia of Algorithms
Marek Chrobak
2008 J jnl
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems
CoRR
Marek Chrobak, Christoph Dürr, Mathilde Hurand, Julien Robert
2008 C conf
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems.
AAIM
Marek Chrobak, Christoph Dürr, Mathilde Hurand, Julien Robert
2008 J jnl
Competitive Analysis of Scheduling Algorithms for Aggregated Links.
Algorithmica
Wojciech Jawor, Marek Chrobak, Christoph Dürr
2008 B conf
Dynamic Thermal Management through Task Scheduling.
ISPASS
Jun Yang, Xiuyi Zhou, Marek Chrobak, Youtao Zhang, Lingling Jin
2008 B conf
Experimental Analysis of Scheduling Algorithms for Aggregated Links.
WAOA
Wojciech Jawor, Marek Chrobak, Mart L. Molle
2008 J jnl
Generalized Whac-a-Mole
CoRR
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Jakub Lopuszanski, Grzegorz Stachowiak
2008 J jnl
Incremental Medians via Online Bidding.
Algorithmica
Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young
2008 A* conf
Policy-Aware Topologies for Efficient Inter-Domain Routing Evaluations.
INFOCOM
Yihua He, Michalis Faloutsos, Srikanth V. Krishnamurthy, Marek Chrobak
2008 B conf
Randomized Algorithms for Buffer Management with 2-Bounded Delay.
WAOA
Marcin Bienkowski, Marek Chrobak, Lukasz Jez
2008 J jnl
SIGACT news online algorithms column 13: 2007 - an offine perspective.
SIGACT News
Marek Chrobak
2008 — ch.
Work-Function Algorithm for k Servers.
Encyclopedia of Algorithms
Marek Chrobak
2007 B conf
Algorithmic Approaches to Selecting Control Clones in DNA Array Hybridization Experiments.
APBC
Qi Fu, Elizabeth Bent, James Borneman, Marek Chrobak, Neal E. Young
2007 J jnl
Algorithmic Approaches to Selecting Control Clones in DNA Array Hybridization Experiments.
J. Bioinform. Comput. Biol.
Qi Fu, Elizabeth Bent, James Borneman, Marek Chrobak, Neal E. Young
2007 B conf
Better Bounds for Incremental Medians.
WAOA
Marek Chrobak, Mathilde Hurand
2007 J jnl
Competitiveness via primal-dual.
SIGACT News
Marek Chrobak
2007 A conf
Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines.
RTSS
Marek Chrobak, Mathilde Hurand, Jirí Sgall
2007 J jnl
Improved online algorithms for buffer management in QoS switches.
ACM Trans. Algorithms
Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý
2007 J jnl
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help.
SIAM J. Comput.
Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý
2007 A conf
Polynomial Time Algorithms for Minimum Energy Scheduling.
ESA
Philippe Baptiste, Marek Chrobak, Christoph Dürr
2007 J jnl
Sampling large Internet topologies for simulation purposes.
Comput. Networks
Vaishnavi Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Jun-Hong Cui, Li Lao, Allon G. Percus
2007 J jnl
The Wake-Up Problem in MultiHop Radio Networks.
SIAM J. Comput.
Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski
2007 J jnl
The complexity of mean flow time scheduling problems with release times.
J. Sched.
Philippe Baptiste, Peter Brucker, Marek Chrobak, Christoph Dürr, Svetlana A. Kravchenko, Francis Sourd
2006 J jnl
2005: an offline persepctive.
SIGACT News
Marek Chrobak
2006 J jnl
A Note on Scheduling Equal-Length Jobs to Maximize Throughput.
J. Sched.
Marek Chrobak, Christoph Dürr, Wojciech Jawor, Lukasz Kowalik, Maciej Kurowski
2006 B conf
A low-cost memory remapping scheme for address bus protection.
PACT
Lan Gao, Jun Yang, Marek Chrobak, Youtao Zhang, San Nguyen, Hsien-Hsin S. Lee
2006 B conf
Competitive Analysis of Scheduling Algorithms for Aggregated Links.
LATIN
Wojciech Jawor, Marek Chrobak, Christoph Dürr
2006 B conf
Oblivious Medians Via Online Bidding.
LATIN
Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young
2006 J jnl
Online competitive algorithms for maximizing weighted throughput of unit jobs.
J. Discrete Algorithms
Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Jirí Sgall, Tomás Tichý
2006 J jnl
SIGACT news online algorithms column 10: competitiveness via doubling.
SIGACT News
Marek Chrobak, Claire Kenyon-Mathieu
2006 J jnl
The Complexity of Mean Flow Time Scheduling Problems with Release Times
CoRR
Philippe Baptiste, Peter Brucker, Marek Chrobak, Christoph Dürr, Svetlana A. Kravchenko, Francis Sourd
2006 J jnl
The reverse greedy algorithm for the metric
Inf. Process. Lett.
Marek Chrobak, Claire Kenyon, Neal E. Young
2005 J jnl
Oblivious Medians via Online Bidding
CoRR
Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young
2005 B conf
Reducing Large Internet Topologies for Faster Simulations.
NETWORKING
Vaishnavi Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Li Lao, Jun-Hong Cui, Allon G. Percus
2005 J jnl
SIGACT news online algorithms column 8.
SIGACT News
Marek Chrobak
2005 Misc conf
The Reverse Greedy Algorithm for the Metric
COCOON
Marek Chrobak, Claire Kenyon, Neal E. Young
2005 J jnl
The greedy algorithm for the minimum common string partition problem.
ACM Trans. Algorithms
Marek Chrobak, Petr Kolman, Jirí Sgall
2005 J jnl
The reverse greedy algorithm for the metric k-median problem
CoRR
Marek Chrobak, Claire Kenyon, Neal E. Young
2004 J jnl
A Note on Scheduling Equal-Length Jobs to Maximize Throughput
CoRR
Marek Chrobak, Christoph Dürr, Wojciech Jawor, Lukasz Kowalik, Maciej Kurowski
2004 J jnl
A princess swimming in the fog looking for a monster cow.
SIGACT News
Marek Chrobak
2004 J jnl
A randomized algorithm for gossiping in radio networks.
Networks
Marek Chrobak, Leszek Gasieniec, Wojciech Rytter
2004 J jnl
Coordination mechanisms for congestion games.
SIGACT News
Marek Chrobak, Elias Koutsoupias
2004 A conf
Errata to Analysis of the Harmonic Algorithm for Three Servers.
STACS
Marek Chrobak, Jirí Sgall
2004 A conf
Improved Online Algorithms for Buffer Management in QoS Switches.
ESA
Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý
2004 A conf
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.
STACS
Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jirí Sgall, Tomás Tichý
2004 A* conf
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help.
ICALP
Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý
2004 J jnl
Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time
CoRR
Philippe Baptiste, Marek Chrobak, Christoph Dürr, Francis Sourd
2004 J jnl
Preemptive scheduling of equal-length jobs to maximize weighted throughput.
Oper. Res. Lett.
Philippe Baptiste, Marek Chrobak, Christoph Dürr, Wojciech Jawor, Nodari Vakhania
2004 J jnl
SIGACT news online algorithms column 2.
SIGACT News
Marek Chrobak
2004 J jnl
SIGACT news online algorithms column 4.
SIGACT News
Marek Chrobak
2004 — conf
The Greedy Algorithm for the Minimum Common String Partition Problem.
APPROX-RANDOM
Marek Chrobak, Petr Kolman, Jirí Sgall
2004 A* conf
The wake-up problem in multi-hop radio networks.
SODA
Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski
2004 J jnl
The weighted 2-server problem.
Theor. Comput. Sci.
Marek Chrobak, Jirí Sgall
2003 A conf
Analysis of the Harmonic Algorithm for Three Servers.
STACS
Marek Chrobak, Jirí Sgall
2003 B conf
Faster Algorithms for
MFCS
Robert Benkoczi, Binay K. Bhattacharya, Marek Chrobak, Lawrence L. Larmore, Wojciech Rytter
2003 J jnl
More on randomized on-line algorithms for caching.
Theor. Comput. Sci.
Marek Chrobak, Elias Koutsoupias, John Noga
2003 J jnl
On tiling under tomographic constraints.
Theor. Comput. Sci.
Marek Chrobak, Peter Couperus, Christoph Dürr, Gerhard J. Woeginger
2003 J jnl
Preemptive scheduling in overloaded systems.
J. Comput. Syst. Sci.
Marek Chrobak, Leah Epstein, John Noga, Jirí Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania
2003 J jnl
SIGACT news online algorithms column 1.
SIGACT News
Marek Chrobak
2002 J jnl
Fast broadcasting and gossiping in radio networks.
J. Algorithms
Marek Chrobak, Leszek Gasieniec, Wojciech Rytter
2002 J jnl
More on random walks, electrical networks, and the harmonic k-server algorithm.
Inf. Process. Lett.
Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan
2002 A* conf
Preemptive Scheduling in Overloaded Systems.
ICALP
Marek Chrobak, Leah Epstein, John Noga, Jirí Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania
2002 J jnl
Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput
CoRR
Philippe Baptiste, Marek Chrobak, Christoph Dürr, Wojciech Jawor, Nodari Vakhania
2002 J jnl
Solution of a problem in DNA computing.
Theor. Comput. Sci.
Eric Anderson, Marek Chrobak, John Noga, Jirí Sgall, Gerhard J. Woeginger
2002 J jnl
The 3-server problem in the plane.
Theor. Comput. Sci.
Wolfgang W. Bein, Marek Chrobak, Lawrence L. Larmore
2001 J jnl
A Note on Tiling under Tomographic Constraints
CoRR
Marek Chrobak, Peter Couperus, Christoph Dürr, Gerhard J. Woeginger
2001 Misc conf
A Randomized Algorithm for Gossiping in Radio Networks.
COCOON
Marek Chrobak, Leszek Gasieniec, Wojciech Rytter
2001 — conf
Probe selection algorithms with applications in the analysis of microbial communities.
ISMB (Supplement of Bioinformatics)
James Borneman, Marek Chrobak, Gianluca Della Vedova, Andres Figueroa, Tao Jiang
2001 J jnl
Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms.
Theor. Comput. Sci.
Marek Chrobak, Christoph Dürr
2001 A* conf
The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts.
ICALP
Marek Chrobak, János Csirik, Csanád Imreh, John Noga, Jirí Sgall, Gerhard J. Woeginger
2001 B conf
The k-Median Problem for Directed Trees.
MFCS
Marek Chrobak, Lawrence L. Larmore, Wojciech Rytter
2000 J jnl
A Randomized Algorithm for Two Servers on the Line.
Inf. Comput.
Yair Bartal, Marek Chrobak, Lawrence L. Larmore
2000 J jnl
A simple analysis of the harmonic algorithm for two servers.
Inf. Process. Lett.
Marek Chrobak, Jirí Sgall
2000 J jnl
Competitive Algorithms for Relaxed List Update and Multilevel Caching.
J. Algorithms
Marek Chrobak, John Noga
2000 J jnl
Competitive analysis of randomized paging algorithms.
Theor. Comput. Sci.
Dimitris Achlioptas, Marek Chrobak, John Noga
2000 J jnl
Computing simple paths among obstacles.
Comput. Geom.
Qi Cheng, Marek Chrobak, Gopalakrishnan Sundaram
2000 A* conf
Fast Broadcasting and Gossiping in Radio Networks.
FOCS
Marek Chrobak, Leszek Gasieniec, Wojciech Rytter
2000 A conf
The Weighted 2-Server Problem.
STACS
Marek Chrobak, Jirí Sgall
1999 J jnl
LRU Is Better than FIFO.
Algorithmica
Marek Chrobak, John Noga
1999 J jnl
Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms
CoRR
Christoph Dürr, Marek Chrobak
1999 J jnl
Reconstructing hv-Convex Polyominoes from Orthogonal Projections
CoRR
Christoph Dürr, Marek Chrobak
1999 J jnl
Reconstructing hv-Convex Polyominoes from Orthogonal Projections.
Inf. Process. Lett.
Marek Chrobak, Christoph Dürr
1999 A conf
The 3-Server Problem in the Plane.
ESA
Wolfgang W. Bein, Marek Chrobak, Lawrence L. Larmore
1998 A conf
A Randomized Algorithm for Two Servers on the Line (Extended Abstract).
ESA
Yair Bartal, Marek Chrobak, Lawrence L. Larmore
1998 A* conf
Competive Algorithms for Multilevel Caching and Relaxed List Update (Extended Abstract).
SODA
Marek Chrobak, John Noga
1998 A* conf
LRU is Better than FIFO.
SODA
Marek Chrobak, John Noga
1998 J jnl
Minimum-width grid drawings of plane graphs.
Comput. Geom.
Marek Chrobak, Shin-Ichi Nakano
1998 B conf
Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms.
MFCS
Marek Chrobak, Christoph Dürr
1997 J jnl
A Better Lower Bound on the Competitive Ratio of the Randomized 2-Server Problem.
Inf. Process. Lett.
Marek Chrobak, Lawrence L. Larmore, Carsten Lund, Nick Reingold
1997 J jnl
Convex Grid Drawings of 3-Connected Planar Graphs.
Int. J. Comput. Geom. Appl.
Marek Chrobak, Goos Kant
1997 J jnl
Page Migration Algorithms Using Work Functions.
J. Algorithms
Marek Chrobak, Lawrence L. Larmore, Nick Reingold, Jeffery R. Westbrook
1996 — conf
Bibliography on Competitive Algorithms.
Online Algorithms
Marek Chrobak, John Noga
1996 A conf
Competive Analysis of Randomized Paging Algorithms.
ESA
Dimitris Achlioptas, Marek Chrobak, John Noga
1996 — conf
Convex Drawings of Graphs in Two and Three Dimensions (Preliminary Version).
SCG
Marek Chrobak, Michael T. Goodrich, Roberto Tamassia
1996 — conf
Metrical Task Systems, the Server Problem and the Work Function Algorithm.
Online Algorithms
Marek Chrobak, Lawrence L. Larmore
1995 J jnl
A Linear-Time Algorithm for Drawing a Planar Graph on a Grid.
Inf. Process. Lett.
Marek Chrobak, T. H. Payne
1994 J jnl
Generosity Helps or an 11-Competitive Algorithm for Three Servers.
J. Algorithms
Marek Chrobak, Lawrence L. Larmore
1994 A conf
Minimum-Width Grid Drawings of Plane Graphs.
GD
Marek Chrobak, Shin-Ichi Nakano
1994 J jnl
Two Results on Linear Embeddings of Complete Binary Trees.
Theor. Comput. Sci.
Marek Chrobak, Wojciech Rytter
1993 B conf
Page Migration Algorithms Using Work Functions.
ISAAC
Marek Chrobak, Lawrence L. Larmore, Nick Reingold, Jeffery R. Westbrook
1992 A* conf
Generosity Helps, or an 11-Competitive Algorithm for Three Servers.
SODA
Marek Chrobak, Lawrence L. Larmore
1992 J jnl
Harmonic is 3-Competitive for Two Servers.
Theor. Comput. Sci.
Marek Chrobak, Lawrence L. Larmore
1991 J jnl
A New Approach to the Server Problem.
SIAM J. Discret. Math.
Marek Chrobak, Lawrence L. Larmore
1991 J jnl
A Note on the Server Problem and a Benevolent Adversary.
Inf. Process. Lett.
Marek Chrobak, Lawrence L. Larmore
1991 J jnl
An Efficient Parallel Algorithm for Computing a Large Independent Set in Planar Graph.
Algorithmica
Marek Chrobak, Joseph Naor
1991 J jnl
An Optimal On-Line Algorithm for k-Servers on Trees.
SIAM J. Comput.
Marek Chrobak, Lawrence L. Larmore
1991 J jnl
Connectivity vs. Reachability
Inf. Comput.
Marek Chrobak, Howard J. Karloff, Tomasz Radzik
1991 A* conf
Efficient Sequential and Parallel Algorithms for Computing Recovery Points in Trees and Paths.
SODA
Marek Chrobak, David Eppstein, Giuseppe F. Italiano, Moti Yung
1991 J jnl
New Results on Server Problems.
SIAM J. Discret. Math.
Marek Chrobak, Howard J. Karloff, T. H. Payne, Sundar Vishwanathan
1991 J jnl
On Fast Algorithms for Two Servers.
J. Algorithms
Marek Chrobak, Lawrence L. Larmore
1991 J jnl
Planar Orientations with Low Out-degree and Compaction of Adjacency Matrices.
Theor. Comput. Sci.
Marek Chrobak, David Eppstein
1991 — conf
The Server Problem and On-Line Games.
On-Line Algorithms
Marek Chrobak, Lawrence L. Larmore
1990 J jnl
A Data Structure Useful for Finding Hamiltonian Cycles.
Theor. Comput. Sci.
Marek Chrobak, Tomasz Szymacha, Adam Krawczyk
1990 J jnl
Improved Edge-Coloring Algorithms for Planar Graphs.
J. Algorithms
Marek Chrobak, Takao Nishizeki
1990 A* conf
New Results on Server Problems.
SODA
Marek Chrobak, Howard J. Karloff, T. H. Payne, Sundar Vishwanathan
1990 B conf
On Fast Algorithms for Two Servers.
MFCS
Marek Chrobak, Lawrence L. Larmore
1989 J jnl
A lower bound on the size of universal sets for planar graphs.
SIGACT News
Marek Chrobak, Howard J. Karloff
1989 B conf
An Efficient Parallel Algorithm for Computing a Large Independent Set in a Plan Graph.
SPAA
Marek Chrobak, Joseph Naor
1989 J jnl
Fast Algorithms for Edge-Coloring Planar Graphs.
J. Algorithms
Marek Chrobak, Moti Yung
1989 J jnl
Optimal Parallel 5-Colouring of Planar Graphs.
SIAM J. Comput.
Torben Hagerup, Marek Chrobak, Krzysztof Diks
1989 B conf
Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw-Free Graphs.
WADS
Marek Chrobak, Joseph Naor, Mark B. Novick
1988 J jnl
A Note on Random Sampling.
Inf. Process. Lett.
Marek Chrobak, Richard Harter
1988 — conf
Fast Parallel and Sequential Algorithms for Edge-Coloring Planar Graphs.
AWOC
Marek Chrobak, Moti Yung
1988 J jnl
On Some Packing Problem Related to Dynamic Storage Allocation.
RAIRO Theor. Informatics Appl.
Marek Chrobak, Maciej Slusarek
1988 J jnl
On common edges in optimal solutions to traveling salesman and other optimization problems.
Discret. Appl. Math.
Marek Chrobak, Svatopluk Poljak
1988 J jnl
k+1 Heads Are Better than k for PDAs.
J. Comput. Syst. Sci.
Marek Chrobak, Ming Li
1987 A* conf
Parallel 5-Colouring of Planar Graphs.
ICALP
Torben Hagerup, Marek Chrobak, Krzysztof Diks
1987 J jnl
Remarks on String-Matching and One-Way Multihead Automata.
Inf. Process. Lett.
Marek Chrobak, Wojciech Rytter
1987 B conf
Saturating Flows in Networks.
FCT
Bogdan S. Chlebus, Marek Chrobak, Krzysztof Diks
1986 J jnl
Finite Automata and Unary Languages.
Theor. Comput. Sci.
Marek Chrobak
1986 J jnl
Hierarchies of One-Way Multihead Automata Languages.
Theor. Comput. Sci.
Marek Chrobak
1986 B conf
Unique Deciperability for Partially Commutative Alphabet (Extended Abstract).
MFCS
Marek Chrobak, Wojciech Rytter
1986 A* conf
k+1 Heads Are Better than k for PDA's
FOCS
Marek Chrobak, Ming Li
1985 J jnl
A Characterization of Reversal-Bounded Multipushdown Machine Languages.
Theor. Comput. Sci.
Wojciech Rytter, Marek Chrobak
1985 A* conf
Hierarchies of One-Way Multihead Automata Languages.
ICALP
Marek Chrobak
1985 J jnl
Variations on the Technique of Duris and Galil.
J. Comput. Syst. Sci.
Marek Chrobak
1984 J jnl
A Note on Bounded-Reversal Multipushdown Machines.
Inf. Process. Lett.
Marek Chrobak
1984 B conf
Nondeterminism Is Essential for Two-Way Counter Machines.
MFCS
Marek Chrobak
1984 J jnl
Probabilistic Turing Machines and Recursively Enumerable Dedekind Cuts.
Inf. Process. Lett.
Marek Chrobak, Bogdan S. Chlebus