3 papers
cs.DS2026
Primal-Dual Online Algorithms for the Parking Permit Problem
Christian Coester, Alex Turoczy
The Parking Permit Problem (PPP), first studied by Meyerson, is a classic online problem generalizing the ski rental problem. We re-examine the PPP using the primal-dual scheme, ob…
cs.DS2026
Learning-Augmented Online Minimization with Dual Predictions
Christian Coester, Alexa Tudose, Alexander Turoczy
We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theo…
cs.DS2025
Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach
Alexander Turoczy, Young-San Lin
We study the online multi-level aggregation problem with deadlines (MLAP-D) introduced by Bienkowski et al. (ESA 2016, OR 2020). In this problem, requests arrive over time at the v…