research
∙
05/30/2023
A General Framework for Learning-Augmented Online Allocation
Online allocation is a broad class of problems where items arriving onli...
share
research
∙
04/13/2023
Beyond the Quadratic Time Barrier for Network Unreliability
Karger (STOC 1995) gave the first FPTAS for the network (un)reliability ...
research
∙
11/10/2022
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
We give an almost-linear time algorithm for the Steiner connectivity aug...
research
∙
10/13/2022
Online Algorithms for the Santa Claus Problem
The Santa Claus problem is a fundamental problem in fair division: the g...
research
∙
06/11/2022
Online Paging with Heterogeneous Cache Slots
It is natural to generalize the k-Server problem by allowing each reques...
research
∙
05/18/2022
Customizing ML Predictions for Online Algorithms
A popular line of recent research incorporates ML advice in the design o...
research
∙
05/10/2022
Edge Connectivity Augmentation in Near-Linear Time
We give an Õ(m)-time algorithm for the edge connectivity augmentation pr...
research
∙
03/01/2022
Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time
In this paper, we introduce a robust notion of (1+ϵ)-approximate (s, t)-...
research
∙
12/22/2021
Online Graph Algorithms with Predictions
Online algorithms with predictions is a popular and elegant framework fo...
research
∙
11/17/2021
A Hitting Set Relaxation for k-Server and an Extension to Time-Windows
We study the k-server problem with time-windows. In this problem, each r...
research
∙
11/17/2021
Minimum Cuts in Directed Graphs via Partial Sparsification
We give an algorithm to find a minimum cut in an edge-weighted directed ...
research
∙
11/09/2021
Gomory-Hu Tree in Subcubic Time
In 1961, Gomory and Hu showed that the max-flow values of all n 2 pairs ...
research
∙
11/03/2021
Augmenting Edge Connectivity via Isolating Cuts
We give an algorithm for augmenting the edge connectivity of an undirect...
research
∙
11/03/2021
Approximate Gomory-Hu Tree Is Faster Than n-1 Max-Flows
The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data s...
research
∙
11/03/2021
Deterministic Min-cut in Poly-logarithmic Max-flows
We give a deterministic algorithm for finding the minimum (weight) cut o...
research
∙
06/04/2021
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
We give an n^2+o(1)-time algorithm for finding s-t min-cuts for all pair...
research
∙
05/05/2021
Universal Algorithms for Clustering
This paper presents universal algorithms for clustering problems, includ...
research
∙
04/16/2021
Minimum Cuts in Directed Graphs via √(n) Max-Flows
We give an algorithm to find a mincut in an n-vertex, m-edge weighted di...
research
∙
03/31/2021
Vertex Connectivity in Poly-logarithmic Max-flows
The vertex connectivity of an m-edge n-vertex undirected graph is the sm...
research
∙
10/17/2020
Aggregated Deletion Propagation for Counting Conjunctive Query Answers
We investigate the computational complexity of minimizing the source sid...
research
∙
06/17/2020
Caching with Time Windows and Delays
We consider two generalizations of the classical weighted paging problem...
research
∙
06/16/2020
Online Algorithms for Weighted Paging with Predictions
In this paper, we initiate the study of the weighted paging problem with...
research
∙
06/02/2020
Sparsification of Balanced Directed Graphs
Sparsification, where the cut values of an input graph are approximately...
research
∙
05/17/2020
Robust Algorithms for TSP and Steiner Tree
Robust optimization is a widely studied area in operations research, whe...
research
∙
07/23/2019
Generalized Deletion Propagation on Counting Conjunctive Query Answers
We investigate the computational complexity of minimizing the source sid...
research
∙
04/26/2019
Retracting Graphs to Cycles
We initiate the algorithmic study of retracting a graph into a cycle in ...
research
∙
03/19/2019
Faster Algorithms for the Geometric Transportation Problem
Let R and B be two point sets in R^d, with |R|+ |B| = n and where d is a...
research
∙
11/17/2018
Pacing Equilibrium in First-Price Auction Markets
In ad auctions--the prevalent monetization mechanism of Internet compani...
research
∙
02/08/2018