14:00
15:00

[gt.go] - "Making Online Algorithms Semi-Online" by Matthias Gehnen

/Exposé /Talk/

In the classical understanding, an online algorithm gets the instance piece by piece and needs to make some action for every piece of the instance without knowing what comes next. While this is practical for many problems, for some it is not. Therefore in recent years, many variants of online problems are studied which relax the setting. In this talk, we will discuss some variants:

A common way to present graphs in an online fashion is by presenting it vertex-wise, with all the edges that are induced by the already presented vertices. However, if an algorithm must decide if each presented vertex is part of a solution set or not, it is easy to find examples for basically every problem that show that the approximation ratio of the online algorithm is arbitrary bad in comparison to an optimal solution (this is usually called competitive ratio). A way to relax this condition is to not enforce the decision whenever the vertex is presented, but instead only when some property is no longer given. For example, for an online Feedback Vertex Set, it is sensible that the graph is presented vertex-wise, and the online algorithm only needs to add a vertex to the solution set as soon as there is an uncovered circle. If the circle is covered, the instance continues. This concept can be found with the name "Late Accept" or "Delayed Decision". We will mainly discuss the Feedback Vertex Set as an example, which has a competitive ratio of something between four and five. It is even possible to delay those decisions more by adding a modification called "Reservations" [1].

Another way of relaxing the online setting is by letting the algorithm know about the vague future. For a knapsack problem, this means that the algorithm gets the whole instance in advance, but only with rough estimates about each item size - which for example can vary of the actual sizes by some percentage. While there is no chance for an online knapsack algorithm to achieve any competitive ratio without modification, this estimates actually help. Interestingly, the competitive ratio does not degrade smoothly from an "good" competive ratio when the estimate is good to a high ratio when the estimate gets worse - instead, there are even jumps in the quality of an algorithm when the estimates degrade [2].

[1] Delaying Decisions and Reservation Costs; E. Burjons, F. Frei, M. Gehnen, H. Lotze, D. Mock, P. Rossmanith; COCOON 2023
[2] Online Simple Knapsack with Bounded Predictions; M. Gehnen, H. Lotze, P. Rossmanith; STACS 2024

[Matthias Gehnen ] (RWTH Aachen )
https://tcs.rwth-aachen.de/~gehnen/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178