Online Algorithms for Configuration Games
Polish National Science Centre grant 2022/45/B/ST6/00559, 2023–2027
The goal of this project is to deliver new algorithmic methods for online optimization. The main focus are on online optimization problems, where the goal is to maintain a changeable state (a configuration) that allows to cheaply serve a sequence of unpredictable requests. To reduce the service cost, it is possible to change the configuration to another one, potentially better suited to the requests, but such choices have to be made without the knowledge of future requests.
An example of a configuration problem occurs in a datacenter containing some number of tightly connected physical machines, each having a fixed capacity that allows it to run a specific number of virtual machines (VMs). In the runtime, pairs of VMs communicate: if such pair is running on a single physical machine, then the communication is free, otherwise it incurs a certain cost corresponding to induced network load and latency. The core hardness is caused by the online nature: the communication requests appear one by one. In response to a request, to minimize the overall communication cost, a partitioning algorithm may modify the placement of VMs (the configuration); this is technically feasible but comes with a certain cost. Importantly, these algorithmic decisions have to be made solely on the basis of past communication requests, and without the knowledge about the future ones.
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 33rd Int. Joint Conference on Artificial Intelligence (IJCAI 2024)
Julien Dallot, Maciej Pacut, Marcin Bienkowski, Darya Melnyk, Stefan Schmid: Online Minimum Linear Arrangement of Cliques and Lines, accepted to 44th IEEE Int. Conf. on Distributed Computing Systems (ICDCS 2024)
Marcin Bienkowski, Guy Even: An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement, 41st Int. Symp. on Theoretical Aspects of Computer Science (STACS 2024), 15:1–15:19, DOI: 10.4230/LIPIcs.STACS.2024.15
Marcin Bienkowski, Stefan Schmid: A Subquadratic Bound for Online Bisection, 41st Int. Symp. on Theoretical Aspects of Computer Science (STACS 2024), 14:1-14:18, DOI: 10.4230/LIPIcs.STACS.2024.14
2023
Mateusz Basiak, Marcin Bienkowski, Agnieszka Tatarczuk: An Improved Deterministic Algorithm For the Online Min-Sum Set Cover Problem, Workshop on Approximation and Online Algorithms (WAOA 2023), 45–58, best paper award, DOI: 10.1007/978-3-031-49815-2_4
Marcin Bienkowski, David Fuchssteiner, Stefan Schmid: Optimizing Reconfigurable Optical Datacenters: The Power of Randomization, The International Conference for High Performance Computing, Networking, Storage, and Analysis (SC 2023), 83:1–83:11, 2023, DOI: 10.1145/3581784.3607057