Marcin Bieńkowski
About / current / recent duties
Associate professor in Combinatorial Optimization Group at Institute of Computer Science, University of Wrocław
Principal Investigator of National Science Centre grant: Online algorithms for configuration games, 2023-2027
PC co-chair of WAOA 2024, PC member APPROX 2023
Local organizer of IPCO 2024
Research topics
I'm generally interested in online algorithms, with a special focus on graph problems, server problems and task systems, tradeoffs achievable by waiting or request reordering, and applications to computer networks and logistics.
PhD Students / Postdocs
Agnieszka Tatarczuk
Mateusz Basiak
Artur Kraska (graduated 2022)
Paweł Schmidt (graduated 2022)
Hsiang-Hsuan (Alison) Liu (postdoc 2017-2019)
Maciej Pacut (graduated 2019)
Łukasz Jeż (informal advisor, graduated 2011)
Past duties
PC member of FCT 2015, WAOA 2019, SOFSEM 2021 and SIROCCO 2021
Local organizer of ICALP 2007, ALGO 2014, and SIROCCO 2021
PI in grant Algorithmic online optimization for graph problems, 2017-2022
PI in grant Online algorithms for fundamental network problems, 2014-2017
PI in grant Approximation algorithms under uncertainty, 2010-2013
Selected publications
M. Bienkowski, G. Even: An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement, STACS 2024
M. Bienkowski, M. Mucha: An Improved Algorithm For Online Min-Sum Set Cover, AAAI 2023, slides
M. Bienkowski, M. Böhm, J. Byrka, J. Marcinkowski: Online Facility Location with Linear Delay. APPROX 2022, slides
M. Bienkowski, A. Kraska and H.-H. Liu: Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times. ICALP 2021
M. Bienkowski, B. Feldkord, P. Schmidt: A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location. STACS 2021, slides
M. Bienkowski, J. Byrka, C. Coester, Ł. Jeż: Unbounded lower bound for k-server against weak adversaries. STOC 2020, slides
M. Bienkowski, M. Pacut, K. Piecuch: An Optimal Algorithm for Online Multiple Knapsack. ICALP 2020
M. Bienkowski, M. Böhm, J. Byrka, M. Chrobak, C. Dürr, L. Folwarczný, Ł. Jeż, J. Sgall, N. Thang, P. Veselý: Online Algorithms for Multi-Level Aggregation. Oper. Res. 2020 + ESA 2016, slides
M. Bienkowski, J. Byrka, M. Mucha: Dynamic beats fixed: On phase-based algorithms for file migration. TALG 2019 + ICALP 2017, slides
M. Bienkowski, T. Jurdzinski, M. Korzeniowski, D. Kowalski: Distributed Online and Stochastic Queuing on a Multiple Access Channel. TALG 2018
M. Bienkowski, N. Sarrar, S. Schmid, S. Uhlig: Online Aggregation of the Forwarding Information Base. Trans. Netw. 2018
M. Bienkowski, M. Klonowski, M. Korzeniowski, D. Kowalski: Randomized Mutual Exclusion on a Multiple Access Channel. Dist. Comp. 2016 + STACS 2010
M. Bienkowski, J. Byrka, M. Chrobak, N. Dobbs, T. Nowicki, M. Sviridenko, G. Świrszcz and N. Young: Approximation Algorithms for the Joint Replenishment Problem with Deadlines. J. Sched. 2015 + ICALP 2013
M. Bienkowski, J. Byrka, K. Chrobak, T. Jurdzinski, D. Kowalski: Provable Fairness for TDMA Scheduling. INFOCOM 2015
M. Bienkowski, J. Byrka, M. Chrobak, Ł. Jeż, D. Nogneng, J. Sgall: Better Approximation Bounds for the Joint Replenishment Problem. SODA 2014, slides
M. Bienkowski: An Optimal Lower Bound for Buffer Management in Multi-Queue Switches. Algorithmica 2014 + SODA 2011, slides
M. Bienkowski, A. Feldmann, J. Grassler, G. Schaffrath, S. Schmid: The Wide-Area Virtual Service Migration Problem. Trans. Netw. 2014
M. Bienkowski, M. Chrobak, C. Dürr, M. Hurand, A. Jeż, Ł. Jeż, G. Stachowiak: Collecting Weighted Items from a Dynamic Queue. Algorith. 2013 + SODA 2009
M. Bienkowski, J. Byrka, M. Korzeniowski, F. Meyer auf der Heide: Optimal Algorithms for Page Migration in Dynamic Networks. J. Disc. Alg. 2009
M. Bienkowski, J. Byrka: Bucket Game with Applications to Set Multicover and Dynamic Page Migration. ESA 2005.
M. Bienkowski, M. Korzeniowski, F. Meyer auf der Heide: Dynamic Load Balancing in Distributed Hash Tables. IPTPS 2005
M. Bienkowski, M. Korzeniowski, H. Räcke: A Practical Algorithm for Constructing Oblivious Routing Schemes. SPAA 2003.