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

• Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, Agnieszka Tatarczuk: A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
  
  

2025

• Marcin Bienkowski, Jarosław Byrka, Łukasz Jeż: Online Disjoint Set Covers: Randomization is not Necessary, 42nd Int. Symp. on Theoretical Aspects of Computer Science (STACS 2025), 18:1-18:16, DOI:  10.4230/LIPIcs.STACS.2025.18

• Mathieu Mari, Michal Pawlowski, Runtian Ren, Piotr Sankowski: Online Matching with Delays and Stochastic Arrival Times, Theory of Computing Systems (ToCS), vol 69(12), DOI: 10.1007/s00224-024-10207-6
  
  

2024

• Mathieu Mari, Michał Pawłowski, Runtian Ren, Piotr Sankowski: Online Multi-level Aggregation with Delays and Stochastic Arrivals, 35th Int. Symp. on Algorithms and Computation (ISAAC 2024), 49:1-49:20, DOI: 10.4230/LIPIcs.ISAAC.2024.49

• Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, Bertrand Simon: Contract Scheduling with Distributional and Multiple Advice, 33rd Int. Joint Conference on Artificial  Intelligence (IJCAI 2024), 3652–3660, DOI: 10.24963/ijcai.2024/404

• Julien Dallot, Maciej Pacut, Marcin Bienkowski, Darya Melnyk, Stefan Schmid: Learning Minimum Linear Arrangement of Cliques and Lines, 44th IEEE Int. Conf. on Distributed Computing Systems (ICDCS 2024), 175–185, DOI: 10.1109/ICDCS60910.2024.00025

• 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