Computational and Applied Mathematics seminar

Abstract: 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 two 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 competitive ratio of the online algorithm is arbitrary bad. 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 Online Feedback Vertex Set as an example, which has a competitive ratio of something between four and five [1].

Another classical online problem on graphs is the Graph Exploration Problem: Here every vertex of a given graph must be visited as in the classical TSP setting, but here the graph is not known in the beginning. At every point, an algorithm only knows about the already visited vertices and their neighbors. This however is not necessarily a realistic setting: Usually the structure of the graph (for example underlying road network) is known in advance, but the details are not. One usually has a prediction of how long it takes to traverse through a particular road, but due to road conditions or imprecise maps, one might realize that a road will take slightly longer than expected when arriving at it. To deal with those deviations, it is natural to assume that an agent can adapt to the situation: When realizing that taking a particular road is more expensive than expected, recalculating the tour and taking another road instead is possible.

In a sense, this setting lies in between the offline TSP, and the online problem of graph exploration: it allows some computation at the beginning, but remains an online problem during traversal through the graph. For general graphs, we show that no strategy achieves a competitive ratio better than the accuracy factor of the prediction, which can be matched by a simple algorithm. In addition, we will also have a look at restricted graph classes [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, E. Naquin, R. Klasing; Preprint avilable, 2025