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


2024

2023