Publications

See also DBLP, Google Scholar, and Semantic Scholar sites.

Unpublished

• Marcin Bienkowski, Jarosław Byrka, Łukasz Jeż: Online Disjoint Set Covers: Randomization is not Necessary
  
  

2024

• Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, Bertrand Simon: Contract Scheduling with Distributional and Multiple Advice, accepted to IJCAI 2024

• Julien Dallot, Maciej Pacut, Marcin Bienkowski, Darya Melnyk, Stefan Schmid: Online Minimum Linear Arrangement of Cliques and Lines, ICDCS 2024

• Marcin Bienkowski, Stefan Schmid: A Subquadratic Bound for Online Bisection, STACS 2024, slides

• Marcin Bienkowski, Guy Even: An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement, STACS 2024
  
  

2023

• Mateusz Basiak, Marcin Bienkowski, Agnieszka Tatarczuk: An Improved Deterministic Algorithm For the Online Min-Sum Set Cover Problem, WAOA 2023, best paper award

• Marcin Bienkowski, David Fuchssteiner, Stefan Schmid: Optimizing Reconfigurable Optical Datacenters: The Power of Randomization, SC 2023

• Marcin Bienkowski, Marcin Mucha: An Improved Algorithm For Online Min-Sum Set Cover, AAAI 2023, slides
  
  

2022

• Marcin Bienkowski, Martin Böhm, Jarosław Byrka, Jan Marcinkowski: Online Facility Location with Linear Delay, APPROX 2022, slides

• Chen Avin, Marcin Bienkowski, Iosif Salem, Robert Sama, Stefan Schmid and Paweł Schmidt: Deterministic Self-Adjusting Tree Networks Using Rotor Walks. ICDCS 2021
  
  

2021

• Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jiří Sgall, Pavel Veselý: Improved Analysis of Online Balanced Clustering, WAOA 2021, slides

• Marcin Bienkowski, Artur Kraska and Hsiang-Hsuan Liu: Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times, ICALP 2021

• Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý: New Results on Multi-Level Aggregation, TCS 2021

• Marcin Bienkowski, Björn Feldkord, Paweł Schmidt: A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location, STACS 2021, slides
  
  

2020

• Marcin Bienkowski, Jarosław Byrka, Christian Coester, Łukasz Jeż: Unbounded lower bound for k-server against weak adversaries, STOC 2020, also in HALG 2020, Christian's slides

• Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch: An Optimal Algorithm for Online Multiple Knapsack, ICALP 2020

• Marcin Bienkowski, David Fuchssteiner, Jan Marcinkowski, Stefan Schmid: Online Dynamic b-Matching with Applications to Reconfigurable Datacenter Networks, PERFORMANCE 2020

• Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, Stefan Schmid: Dynamic Balanced Graph Partitioning, SIAM Disc. Math. 2020

• Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, and Pavel Veselý: Online Algorithms for Multi-Level Aggregation, Operation Research 2020, also in ESA 2016

2019

• Marcin Bienkowski, Łukasz Jeż, Paweł Schmidt: Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics, ISAAC 2019, slides

• Marcin Bienkowski, Hsiang-Hsuan Liu: Improved Online Algorithm for The Traveling Repairperson Problem on a Line, MFCS 2019, also in MAPSP 2019, slides

• Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, Elias Koutsoupias: Better Bounds for Online Line Chasing, MFCS 2019, also in HALG 2019

• Marcin Bienkowski, Jaroslaw Byrka and Marcin Mucha: Dynamic beats fixed: On phase-based algorithms for file migration, Trans. Alg. 2019, also in ICALP 2017

2018

• Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, Paweł Schmidt: A Primal-Dual Online Deterministic Algorithm for Matching with Delays
  WAOA 2018, also in MOLI 2018,  Hsiang-Hsuan (Alison)'s slides

• Marcin Bienkowski, Artur Kraska, Paweł Schmidt: Online service with delay on a line, SIROCCO 2018, Paweł's slides

• Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski: Distributed Online and Stochastic Queuing on a Multiple Access Channel, Trans. Alg. 2018, also in DISC 2012

• Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig: Online Aggregation of the Forwarding Information Base: Accounting for Locality and Churn
  Trans. Netw. 2018, also in GLOBECOM 2014 and ICDCS 2014

• Marcin Bienkowski, Martin Böhm, Łukasz Jeż, Paweł Laskoś-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, Pavel Veselý: Logarithmic price of buffer downscaling on line metrics, TCS 2018

2017

• Marcin Bienkowski, Artur Kraska, Paweł Schmidt: A Match in Time Saves Nine: Deterministic Online Matching With Delays, WAOA 2017

• Marcin Bienkowski, Jaroslaw Byrka and Marcin Mucha: Dynamic beats fixed: On phase-based algorithms for file migration, ICALP 2017, also in HALG 2018 and ISMP 2018, slides

• Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, Aleksandra Spyra: Online Tree Caching, SPAA 2017, slides

• Marcin Bienkowski, Artur Kraska, Paweł Schmidt: A Deterministic Algorithm for Online Steiner Tree Leasing, WADS 2017

2016

• Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý: Online Algorithms for Multi-Level Aggregation, ESA 2016, also in MAPSP 2015, slides

• Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, Dariusz R. Kowalski: Randomized Mutual Exclusion on a Multiple Access Channel, Dist. Comp. 2016, also in STACS 2010

• Marcin Bienkowski, Leszek Gąsieniec, Marek Klonowski, Miroslaw Korzeniowski, Bernard Mans, Stefan Schmid, Roger Wattenhofer: Distributed Alarming in the On-Duty and Off-Duty Models, Trans. Netw 2016, also in SIROCCO 2010

2015

• Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Świrszcz, Neal E. Young: Approximation Algorithms for the Joint Replenishment Problem with Deadlines, J. Sched. 2015, also in ICALP 2013

• Marcin Bienkowski, Artur Kraska, Paweł Schmidt: A Randomized Algorithm for Online Scheduling with Interval Conflicts, SIROCCO 2015, Artur's slides

• Marcin Bienkowski, Jaroslaw Byrka, Krzysztof Chrobak, Tomasz Jurdzinski, Dariusz Kowalski: Provable Fairness for TDMA Scheduling, INFOCOM 2015

2014

• Marcin Bienkowski: An Optimal Lower Bound for Buffer Management in Multi-Queue Switches, Algorithmica 2014, also in SODA 2011

• Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Dorian Nogneng, Jiří Sgall: Better Approximation Bounds for the Joint Replenishment Problem, SODA 2014, Marek's slides

• Marcin Bienkowski, Anja Feldmann, Johannes Grassler, Gregor Schaffrath, Stefan Schmid: The Wide-Area Virtual Service Migration Problem: A Competitive Analysis Approach, Trans. Netw. 2014, also in IPTComm 2011

• Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig: Competitive FIB Aggregation without Update Churn, ICDCS 2014

• Nadi Sarrar, Robert Wuttke, Stefan Schmid, Marcin Bienkowski, Steve Uhlig: Leveraging Locality for FIB Aggregation, GLOBECOM 2014

2013

• Marcin Bienkowski, Stefan Schmid: Competitive FIB Aggregation for Independent Prefixes: Online Ski Rental on the Trie, SIROCCO 2013

• Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig: Brief Announcement: Dynamic Forwarding Table Aggregation without Update Churn: The Case of Dependent Prefixes, DISC 2013

• Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Jiří Sgall, Grzegorz Stachowiak: Online Control Message Aggregation in Chain Networks, WADS 2013, also in MAPSP 2013, slides

• Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Świrszcz, Neal E. Young: Approximation Algorithms for the Joint Replenishment Problem with Deadlines, ICALP 2013

• Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak: A φ-Competitive Algorithm for Collecting Items with Increasing Weights from a Dynamic Queue, TCS 2013, also in SODA 2009

• Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak: Collecting Weighted Items from a Dynamic Queue, Algorithmica 2013, also in SODA 2009

• Marcin Bienkowski, Paweł Zalewski: (1,2)-Hamiltonian Completion on a Matching, J. Found. Comp. Sci. 2013

2012

• Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski: Distributed Online and Stochastic Queuing on a Multiple Access Channel, DISC 2012

• Marcin Bienkowski: Migrating and Replicating Data in Networks: CS — R&D 2012

• Marcin Bienkowski, Jarosław Kutyłowski: The k-Resource Problem in Uniform Metric Spaces, TCS 2012, also in WADS 2007

2011

• Marcin Bienkowski, Marek Chrobak, Łukasz Jeż: Randomized Competitive Algorithms for Online Buffer Management in the Adaptive Adversary Model, TCS 2011, also in WAOA 2008

• Marcin Bienkowski: An Optimal Lower Bound for Buffer Management in Multi-Queue Switches, SODA 2011, slides

• Dushyant Arora, Marcin Bienkowski, Anja Feldmann, Gregor Schaffrath, Stefan Schmid: Online Strategies for Intra and Inter Provider Service Migration in Virtual Networks, IPTComm 2011

2010

• Marcin Bienkowski, Stefan Schmid: Online Function Tracking with Generalized Penalties, SWAT 2010

• Marcin Bienkowski, Leszek A. Gąsieniec, Marek Klonowski, Miroslaw Korzeniowski, Stefan Schmid: Event Extent Estimation, SIROCCO 2010

• Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, Dariusz R. Kowalski: Dynamic Sharing of a Multiple Access Channel, STACS 2010

• Marcin Bienkowski, Anja Feldmann, Dan Jurca, Wolfgang Kellerer, Gregor Schaffrath, Stefan Schmid, Joerg Widmer: Competitive Analysis for Service Migration in VNets, VISA@SIGCOMM 2010

• Marcin Bienkowski, André Brinkmann, Marek Klonowski, Miroslaw Korzeniowski: SkewCCC+: A Heterogeneous Distributed Hash Table, OPODIS 2010

2009

• Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak: Collecting Weighted Items from a Dynamic Queue, SODA 2009

• Marcin Bienkowski, Jarosław Byrka, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide: Optimal Algorithms for Page Migration in Dynamic Networks
  J. Disc. Alg. 2009, also in SPAA 2004, STACS 2005 and ESA 2005

• Marcin Bienkowski: Price Fluctuations: To Buy or to Rent, WAOA 2009, slides

2008

• Marcin Bienkowski, Marek Chrobak, Łukasz Jeż: Randomized Algorithms for Buffer Management with 2-Bounded Delay, WAOA 2008

• Marcin Bienkowski, Aleksander Mądry: Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers, LATIN 2008, slides

• Marcin Bienkowski, André Brinkmann, Miroslaw Korzeniowski: Degree 3 Suffices: A Large-Scale Overlay for P2P Networks, OPODIS 2008

2007

• Marcin Bienkowski, Jarosław Kutyłowski: The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces, WADS 2007, slides

2005

• Marcin Bienkowski, Jarosław Byrka: Bucket Game with Applications to Set Multicover and Dynamic Page Migration, ESA 2005

• Marcin Bienkowski, Friedhelm Meyer auf der Heide: Page Migration in Dynamic Networks, MFCS 2005

• Marcin Bienkowski, Miroslaw Korzeniowski, Dynamic Page Migration under Brownian Motion, Euro-Par 2005

• Marcin Bienkowski: Dynamic Page Migration with Stochastic Requests, SPAA 2005

• Marcin Bienkowski, Miroslaw Dynia, Miroslaw Korzeniowski: Improved Algorithms for Dynamic Page Migration, STACS 2005, slides

• Marcin Bienkowski, Miroslaw Korzeniowski: Bounding Communication Cost in Dynamic Load Balancing of Distributed Hash Tables, OPODIS 2005

• Marcin Bienkowski, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide: Dynamic Load Balancing in Distributed Hash Tables, IPTPS 2005

• Marcin Bienkowski, Valentina Damerow, Friedhelm Meyer auf der Heide, Christian Sohler: Average case complexity of Voronoi diagrams of n sites from the unit cube, EuroCG 2005

2004

• Marcin Bienkowski, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide: Fighting Against Two Adversaries: Page Migration in Dynamic Networks, SPAA 2004

2003

• Marcin Bienkowski, Miroslaw Korzeniowski, Harald Räcke: A Practical Algorithm for Constructing Oblivious Routing Schemes, SPAA 2003

PhD Thesis

• Marcin Bienkowski: Page Migration in Dynamic Networks, University of Paderborn, 2005