2 papers
cs.DS2026
A simple Path-based LP Relaxation for Directed Steiner Tree
Kanstantsin Pashkovich, Marta Pozzi, Laura Sanità
We study the Directed Steiner Tree (DST) problem in layered graphs through a simple path-based linear programming relaxation. This relaxation achieves an integrality gap of O(l log…
cs.DS2025
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…