4 papers · 1 filter
To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs
Sander Borst, Moritz Venzin
We study the rent-or-buy variant of the online Steiner forest problem on node- and edge-weighted graphs. For -node graphs with at most non-zero node-weights, and at mo…
Learning-Augmented Online Covering Problems
Afrouz Jabal Ameli, Laura Sanita, Moritz Venzin
We give a very general and simple framework to incorporate predictions on requests for online covering problems in a rigorous and black-box manner. Our framework turns any online a…
Approximation Algorithms for Combinatorial Optimization with Predictions
Antonios Antoniadis, Marek Eliáš, Adam Polak +1
We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic…
Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
Sander Borst, Marek Eliáš, Moritz Venzin
We propose a -competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous b…