45 citations · 92 across the 19 of their papers we have counts for
6 papers · 1 filter
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
Antonios Antoniadis, Christian Coester, Marek Eliáš +2
We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between…
Robust Learning-Augmented Caching: An Experimental Study
Jakub Chłędowski, Adam Polak, Bartosz Szabucki +1
Effective caching is crucial for the performance of modern-day computing systems. A key optimization problem arising in caching -- which item to evict to make room for a new item -…
Nearly-Tight and Oblivious Algorithms for Explainable Clustering
Buddhima Gamlath, Xinrui Jia, Adam Polak +1
We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A -clustering is said to be explainabl…
Knapsack and Subset Sum with Small Items
Adam Polak, Lars Rohwedder, Karol Węgrzycki
Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomi…
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams +1
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in time, and it is widely open whether it has an time algori…
Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees
Adam Polak, Adrian Siwiec, Michał Stobierski
The Euler tour technique is a classical tool for designing parallel graph algorithms, originally proposed for the PRAM model. We ask whether it can be adapted to run efficiently on…