research
∙
07/19/2023
On Dynamic Graph Algorithms with Predictions
We study dynamic algorithms in the model of algorithms with predictions....
share
research
∙
04/04/2023
Mixing predictions for online metric algorithms
A major technique in learning-augmented online algorithms is combining m...
research
∙
11/14/2022
Bellman-Ford is optimal for shortest hop-bounded paths
This paper is about the problem of finding a shortest s-t path using at ...
research
∙
11/09/2022
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
The starting point of this paper is the problem of scheduling n jobs wit...
research
∙
10/06/2022
Paging with Succinct Predictions
Paging is a prototypical problem in the area of online algorithms. It ha...
research
∙
07/26/2022
Learning-Augmented Maximum Flow
We propose a framework for speeding up maximum flow computation by using...
research
∙
03/18/2022
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
We solve the Bin Packing problem in O^*(2^k) time, where k is the number...
research
∙
10/25/2021
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
We study the online problem of minimizing power consumption in systems w...
research
∙
06/30/2021
Nearly-Tight and Oblivious Algorithms for Explainable Clustering
We study the problem of explainable clustering in the setting first form...
research
∙
06/28/2021
Robust Learning-Augmented Caching: An Experimental Study
Effective caching is crucial for the performance of modern-day computing...
research
∙
05/09/2021
Knapsack and Subset Sum with Small Items
Knapsack and Subset Sum are fundamental NP-hard problems in combinatoria...
research
∙
05/06/2021
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is...
research
∙
03/28/2021
Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees
The Euler tour technique is a classical tool for designing parallel grap...
research
∙
09/30/2020
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
The most studied linear algebraic operation, matrix multiplication, has ...
research
∙
08/24/2020
Algorithms and Lower Bounds for the Worker-Task Assignment Problem
We study the problem of assigning workers to tasks where each task has d...
research
∙
04/30/2020
Review of Consumer Wearables in Emotion, Stress, Meditation, Sleep, and Activity Detection and Analysis
Wearables equipped with pervasive sensors enable us to monitor physiolog...
research
∙
03/04/2020
Online metric algorithms with untrusted predictions
Machine-learned predictors, although achieving very good results for inp...
research
∙
12/22/2019
Emotion Recognition Using Wearables: A Systematic Literature Review Work in progress
Wearables like smartwatches or wrist bandsequipped with pervasive sensor...
research
∙
08/30/2019
Equivalences between triangle and range query problems
We define a natural class of range query problems, and prove that all pr...
research
∙
02/26/2018
Online Coloring of Short Intervals
We study the online graph coloring problem restricted to the intersectio...
research
∙
09/28/2017