45 citations · 92 across the 19 of their papers we have counts for
24 papers
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Marek Eliáš, Fabrizio Grandoni, Adam Polak +1
The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent effor…
Warm-Starting All-Pairs Shortest Paths with Predictions
Adam Polak, Jonas Schmidt
One of the three key hypotheses of fine-grained complexity asserts that computing All-Pairs Shortest Paths (APSP) requires cubic time, up to subpolynomial factors, in the worst cas…
On Dynamic Graph Algorithms with Predictions
Jan van den Brand, Sebastian Forster, Yasamin Nazari +1
We study dynamic algorithms in the model of algorithms with predictions. We assume the algorithm is given imperfect predictions regarding future updates, and we ask how such predic…
Mixing predictions for online metric algorithms
Antonios Antoniadis, Christian Coester, Marek Eliáš +2
A major technique in learning-augmented online algorithms is combining multiple algorithms or predictors. Since the performance of each predictor may vary over time, it is desirabl…
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
Kim-Manuel Klein, Adam Polak, Lars Rohwedder
The starting point of this paper is the problem of scheduling jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy…
Bellman-Ford is optimal for shortest hop-bounded paths
Tomasz Kociumaka, Adam Polak
This paper is about the problem of finding a shortest - path using at most edges in edge-weighted graphs. The Bellman--Ford algorithm solves this problem in time,…
Product Portfolio Management in Competitive Environments
Samira Hossein Ghorban, Bardyaa Hesaam
Product diversity is one of the prominent factors for customers' satisfaction, while from the firms' perspective, the additional engineering costs required for product diversity sh…
Learning-Augmented Maximum Flow
Adam Polak, Maksym Zub
We propose a framework for speeding up maximum flow computation by using predictions. A prediction is a flow, i.e., an assignment of non-negative flow values to edges, which satisf…
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Alexandra Lassota, Aleksander Łukasiewicz, Adam Polak
We solve the Bin Packing problem in time, where is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the…
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…
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
The most studied linear algebraic operation, matrix multiplication, has surprisingly fast time algorithms for . On the other hand, the matrix product w…
Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
Aaron Berger, William Kuszmaul, Adam Polak +2
We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of workers and a multiset of tasks,…
Online metric algorithms with untrusted predictions
Antonios Antoniadis, Christian Coester, Marek Elias +2
Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision…
Equivalences between triangle and range query problems
Lech Duraj, Krzysztof Kleiner, Adam Polak +1
We define a natural class of range query problems, and prove that all problems within this class have the same time complexity (up to polylogarithmic factors). The equivalence is v…
Online Coloring of Short Intervals
Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski +2
We study the online graph coloring problem restricted to the intersection graphs of intervals with lengths in . For it is the class of unit interval graphs, and for $σ…
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
Lech Duraj, Marvin Künnemann, Adam Polak
We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called -LCIS: Given integer sequences $X_1,\dots,X…
On an extremal problem for poset dimension
Grzegorz Guśpiel, Piotr Micek, Adam Polak
Let be the largest integer such that every poset on elements has a -dimensional subposet on elements. What is the asymptotics of ? It is easy to see that…
Why is it hard to beat for Longest Common Weakly Increasing Subsequence?
Adam Polak
The Longest Common Weakly Increasing Subsequence problem (LCWIS) is a variant of the classic Longest Common Subsequence problem (LCS). Both problems can be solved with simple quadr…
Counting Triangles in Large Graphs on GPU
Adam Polak
The clustering coefficient and the transitivity ratio are concepts often used in network analysis, which creates a need for fast practical algorithms for counting triangles in larg…