Marcin Bienkowski

112 papers A* 10A 15B 27C 1Journal 51Unranked 7
YearRankTypeTitle / Venue / Authors
2026 J jnl
Online Bisection with Ring Demands.
CoRR
Mateusz Basiak, Marcin Bienkowski, Guy Even, Agnieszka Tatarczuk
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 B ed.
Approximation and Online Algorithms - 22nd International Workshop, WAOA 2024, Egham, UK, September 5-6, 2024, Proceedings
WAOA
Marcin Bienkowski, Matthias Englert
2025 A conf
Online Disjoint Set Covers: Randomization Is Not Necessary.
STACS
Marcin Bienkowski, Jaroslaw Byrka, Lukasz Jez
2024 A conf
A Subquadratic Bound for Online Bisection.
STACS
Marcin Bienkowski, Stefan Schmid
2024 A conf
An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement.
STACS
Marcin Bienkowski, Guy Even
2024 A* conf
Contract Scheduling with Distributional and Multiple Advice.
IJCAI
Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, Bertrand Simon
2024 J jnl
Contract Scheduling with Distributional and Multiple Advice.
CoRR
Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, Bertrand Simon
2024 A conf
Learning Minimum Linear Arrangement of Cliques and Lines.
ICDCS
Julien Dallot, Maciej Pacut, Marcin Bienkowski, Darya Melnyk, Stefan Schmid
2024 J jnl
Learning Minimum Linear Arrangement of Cliques and Lines.
CoRR
Julien Dallot, Maciej Pacut, Marcin Bienkowski, Darya Melnyk, Stefan Schmid
2024 J jnl
Online Disjoint Set Covers: Randomization is not Necessary.
CoRR
Marcin Bienkowski, Jaroslaw Byrka, Lukasz Jez
2023 J jnl
A Subquadratic Bound for Online Bisection.
CoRR
Marcin Bienkowski, Stefan Schmid
2023 A* conf
An Improved Algorithm for Online Min-Sum Set Cover.
AAAI
Marcin Bienkowski, Marcin Mucha
2023 B conf
An Improved Deterministic Algorithm for the Online Min-Sum Set Cover Problem.
WAOA
Mateusz Basiak, Marcin Bienkowski, Agnieszka Tatarczuk
2023 J jnl
An Improved Deterministic Algorithm for the Online Min-Sum Set Cover Problem.
CoRR
Mateusz Basiak, Marcin Bienkowski, Agnieszka Tatarczuk
2023 A conf
Optimizing Reconfigurable Optical Datacenters: The Power of Randomization.
SC
Marcin Bienkowski, David Fuchssteiner, Stefan Schmid
2022 J jnl
An Improved Algorithm For Online Reranking.
CoRR
Marcin Bienkowski, Marcin Mucha
2022 A conf
Deterministic Self-Adjusting Tree Networks Using Rotor Walks.
ICDCS
Chen Avin, Marcin Bienkowski, Iosif Salem, Robert Sama, Stefan Schmid, Pawel Schmidt
2022 J jnl
Deterministic Self-Adjusting Tree Networks Using Rotor Walks.
CoRR
Chen Avin, Marcin Bienkowski, Iosif Salem, Robert Sama, Stefan Schmid, Pawel Schmidt
2022 J jnl
Online B-Matchings for Reconfigurable Datacenters: The Power of Randomization.
CoRR
Marcin Bienkowski, David Fuchssteiner, Stefan Schmid
2022 A conf
Online Facility Location with Linear Delay.
APPROX/RANDOM
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Jan Marcinkowski
2021 A conf
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location.
STACS
Marcin Bienkowski, Björn Feldkord, Pawel Schmidt
2021 B conf
Improved Analysis of Online Balanced Clustering.
WAOA
Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jirí Sgall, Pavel Veselý
2021 J jnl
Improved Analysis of Online Balanced Clustering.
CoRR
Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jirí Sgall, Pavel Veselý
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
Online Facility Location with Linear Delay.
CoRR
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Jan Marcinkowski
2021 A* conf
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times.
ICALP
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu
2021 J jnl
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times.
CoRR
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu
2020 J jnl
A Competitive B-Matching Algorithm for Reconfigurable Datacenter Networks.
CoRR
Marcin Bienkowski, David Fuchssteiner, Jan Marcinkowski, Stefan Schmid
2020 J jnl
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location.
CoRR
Marcin Bienkowski, Björn Feldkord, Pawel Schmidt
2020 A* conf
An Optimal Algorithm for Online Multiple Knapsack.
ICALP
Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
2020 J jnl
An Optimal Algorithm for Online Multiple Knapsack.
CoRR
Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
2020 J jnl
Dynamic Balanced Graph Partitioning.
SIAM J. Discret. Math.
Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, Stefan Schmid
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 Dynamic B-Matching: With Applications to Reconfigurable Datacenter Networks.
SIGMETRICS Perform. Evaluation Rev.
Marcin Bienkowski, David Fuchssteiner, Jan Marcinkowski, Stefan Schmid
2020 A* conf
Unbounded lower bound for k-server against weak adversaries.
STOC
Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez
2019 B conf
An Improved Online Algorithm for the Traveling Repairperson Problem on a Line.
MFCS
Marcin Bienkowski, Hsiang-Hsuan Liu
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
Dynamic Beats Fixed: On Phase-based Algorithms for File Migration.
ACM Trans. Algorithms
Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
2019 B conf
Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics.
ISAAC
Marcin Bienkowski, Lukasz Jez, Pawel Schmidt
2019 J jnl
Unbounded lower bound for k-server against weak adversaries.
CoRR
Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez
2018 B conf
A Primal-Dual Online Deterministic Algorithm for Matching with Delays.
WAOA
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, Pawel Schmidt
2018 J jnl
A Primal-Dual Online Deterministic Algorithm for Matching with Delays.
CoRR
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, Pawel Schmidt
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
Distributed Online and Stochastic Queueing on a Multiple Access Channel.
ACM Trans. Algorithms
Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski
2018 J jnl
Logarithmic price of buffer downscaling on line metrics.
Theor. Comput. Sci.
Marcin Bienkowski, Martin Böhm, Lukasz Jez, Pawel Laskos-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, Pavel Veselý
2018 J jnl
Online Aggregation of the Forwarding Information Base: Accounting for Locality and Churn.
IEEE/ACM Trans. Netw.
Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig
2018 B conf
Online Service with Delay on a Line.
SIROCCO
Marcin Bienkowski, Artur Kraska, Pawel Schmidt
2018 J jnl
Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics.
CoRR
Marcin Bienkowski, Lukasz Jez, Pawel Schmidt
2017 B conf
A Deterministic Algorithm for Online Steiner Tree Leasing.
WADS
Marcin Bienkowski, Artur Kraska, Pawel Schmidt
2017 J jnl
A Match in Time Saves Nine: Deterministic Online Matching With Delays.
CoRR
Marcin Bienkowski, Artur Kraska, Pawel Schmidt
2017 B conf
A Match in Time Saves Nine: Deterministic Online Matching with Delays.
WAOA
Marcin Bienkowski, Artur Kraska, Pawel Schmidt
2017 A* conf
Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration.
ICALP
Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
2017 B conf
Online Tree Caching.
SPAA
Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, Aleksandra Spyra
2016 J jnl
Distributed Alarming in the On-Duty and Off-Duty Models.
IEEE/ACM Trans. Netw.
Marcin Bienkowski, Leszek Gasieniec, Marek Klonowski, Miroslaw Korzeniowski, Bernard Mans, Stefan Schmid, Roger Wattenhofer
2016 J jnl
Dynamic beats fixed: on phase-based algorithms for file migration.
CoRR
Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
2016 J jnl
Logarithmic price of buffer downscaling on line metrics.
CoRR
Marcin Bienkowski, Martin Böhm, Lukasz Jez, Pawel Laskos-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, Pavel Veselý
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 J jnl
Online Tree Caching.
CoRR
Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, Aleksandra Spyra
2016 J jnl
Randomized mutual exclusion on a multiple access channel.
Distributed Comput.
Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, Dariusz R. Kowalski
2015 B conf
A Randomized Algorithm for Online Scheduling with Interval Conflicts.
SIROCCO
Marcin Bienkowski, Artur Kraska, Pawel Schmidt
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 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 A* conf
Provable fairness for TDMA scheduling.
INFOCOM
Marcin Bienkowski, Jaroslaw Byrka, Krzysztof Chrobak, Tomasz Jurdzinski, Dariusz R. Kowalski
2014 J jnl
An Optimal Lower Bound for Buffer Management in Multi-Queue Switches.
Algorithmica
Marcin Bienkowski
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 A conf
Competitive FIB Aggregation without Update Churn.
ICDCS
Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig
2014 B conf
Leveraging locality for FIB aggregation.
GLOBECOM
Nadi Sarrar, Robert Wuttke, Stefan Schmid, Marcin Bienkowski, Steve Uhlig
2014 J jnl
The Wide-Area Virtual Service Migration Problem: A Competitive Analysis Approach.
IEEE/ACM Trans. Netw.
Marcin Bienkowski, Anja Feldmann, Johannes Grassler, Gregor Schaffrath, Stefan Schmid
2013 J jnl
(1, 2)-Hamiltonian Completion on a Matching.
Int. J. Found. Comput. Sci.
Marcin Bienkowski, Pawel Zalewski
2013 J jnl
A
Theor. Comput. Sci.
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak
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
Collecting Weighted Items from a Dynamic Queue.
Algorithmica
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak
2013 B conf
Competitive FIB Aggregation for Independent Prefixes: Online Ski Rental on the Trie.
SIROCCO
Marcin Bienkowski, Stefan Schmid
2013 B conf
Online Control Message Aggregation in Chain Networks.
WADS
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall, Grzegorz Stachowiak
2012 J jnl
Approximation Algorithms for the Joint Replenishment Problem with Deadlines
CoRR
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak
2012 A conf
Distributed Online and Stochastic Queuing on a Multiple Access Channel.
DISC
Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski
2012 J jnl
Migrating and replicating data in networks.
Comput. Sci. Res. Dev.
Marcin Bienkowski
2012 J jnl
The k-resource problem in uniform metric spaces.
Theor. Comput. Sci.
Marcin Bienkowski, Jaroslaw Kutylowski
2011 A* conf
An Optimal Lower Bound for Buffer Management in Multi-Queue Switches.
SODA
Marcin Bienkowski
2011 J jnl
Online Strategies for Intra and Inter Provider Service Migration in Virtual Networks
CoRR
Dushyant Arora, Marcin Bienkowski, Anja Feldmann, Gregor Schaffrath, Stefan Schmid
2011 — conf
Online strategies for intra and inter provider service migration in virtual networks.
IPTComm
Dushyant Arora, Marcin Bienkowski, Anja Feldmann, Gregor Schaffrath, Stefan Schmid
2011 J jnl
Randomized competitive algorithms for online buffer management in the adaptive adversary model.
Theor. Comput. Sci.
Marcin Bienkowski, Marek Chrobak, Lukasz Jez
2010 J jnl
An Optimal Lower Bound for Buffer Management in Multi-Queue Switches
CoRR
Marcin Bienkowski
2010 — conf
Competitive analysis for service migration in VNets.
VISA@SIGCOMM
Marcin Bienkowski, Anja Feldmann, Dan Jurca, Wolfgang Kellerer, Gregor Schaffrath, Stefan Schmid, Joerg Widmer
2010 A conf
Dynamic Sharing of a Multiple Access Channel.
STACS
Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, Dariusz R. Kowalski
2010 J jnl
Dynamic sharing of a multiple access channel
CoRR
Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, Dariusz R. Kowalski
2010 B conf
Event Extent Estimation.
SIROCCO
Marcin Bienkowski, Leszek Gasieniec, Marek Klonowski, Miroslaw Korzeniowski, Stefan Schmid
2010 — conf
Online Function Tracking with Generalized Penalties.
SWAT
Marcin Bienkowski, Stefan Schmid
2010 B conf
SkewCCC+: A Heterogeneous Distributed Hash Table.
OPODIS
Marcin Bienkowski, André Brinkmann, Marek Klonowski, Miroslaw Korzeniowski
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
Optimal algorithms for page migration in dynamic networks.
J. Discrete Algorithms
Marcin Bienkowski, Jaroslaw Byrka, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide
2009 B conf
Price Fluctuations: To Buy or to Rent.
WAOA
Marcin Bienkowski
2008 B conf
Degree 3 Suffices: A Large-Scale Overlay for P2P Networks.
OPODIS
Marcin Bienkowski, André Brinkmann, Miroslaw Korzeniowski
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 B conf
Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers.
LATIN
Marcin Bienkowski, Aleksander Madry
2008 B conf
Randomized Algorithms for Buffer Management with 2-Bounded Delay.
WAOA
Marcin Bienkowski, Marek Chrobak, Lukasz Jez
2007 B conf
The
WADS
Marcin Bienkowski, Jaroslaw Kutylowski
2005 C conf
Average case complexity of Voronoi diagrams of n sites from the unit cube.
EuroCG
Marcin Bienkowski, Valentina Damerow, Friedhelm Meyer auf der Heide, Christian Sohler
2005 B conf
Bounding Communication Cost in Dynamic Load Balancing of Distributed Hash Tables.
OPODIS
Marcin Bienkowski, Miroslaw Korzeniowski
2005 A conf
Bucket Game with Applications to Set Multicover and Dynamic Page Migration.
ESA
Marcin Bienkowski, Jaroslaw Byrka
2005 — conf
Cube Connected Cycles Based Bluetooth Scatternet Formation.
ICN (1)
Marcin Bienkowski, André Brinkmann, Miroslaw Korzeniowski, Orhan Orhan
2005 — conf
Dynamic Load Balancing in Distributed Hash Tables.
IPTPS
Marcin Bienkowski, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide
2005 — conf
Dynamic Page Migration Under Brownian Motion.
Euro-Par
Marcin Bienkowski, Miroslaw Korzeniowski
2005 B conf
Dynamic page migration with stochastic requests.
SPAA
Marcin Bienkowski
2005 A conf
Improved Algorithms for Dynamic Page Migration.
STACS
Marcin Bienkowski, Miroslaw Dynia, Miroslaw Korzeniowski
2005 B conf
Page Migration in Dynamic Networks.
MFCS
Marcin Bienkowski, Friedhelm Meyer auf der Heide
2005 — —
Page migration in dynamic networks.
Marcin Bienkowski
2004 B conf
Fighting against two adversaries: page migration in dynamic networks.
SPAA
Marcin Bienkowski, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide
2003 B conf
A practical algorithm for constructing oblivious routing schemes.
SPAA
Marcin Bienkowski, Miroslaw Korzeniowski, Harald Räcke