16 citations · 69 across the 56 of their papers we have counts for
11 papers · 1 filter
Online Graph Algorithms with Predictions
Yossi Azar, Debmalya Panigrahi, Noam Touitou
Online algorithms with predictions is a popular and elegant framework for bypassing pessimistic lower bounds in competitive analysis. In this model, online algorithms are supplied…
A Hitting Set Relaxation for -Server and an Extension to Time-Windows
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
We study the -server problem with time-windows. In this problem, each request arrives at some point of an -point metric space at time and comes with a deadlin…
Minimum Cuts in Directed Graphs via Partial Sparsification
Ruoxu Cen, Jason Li, Danupon Nanongkai +3
We give an algorithm to find a minimum cut in an edge-weighted directed graph with vertices and edges in time. This improves on the 30 y…
Augmenting Edge Connectivity via Isolating Cuts
Ruoxu Cen, Jason Li, Debmalya Panigrahi
We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS '20). Our algorithm uses poly-logarit…
Approximate Gomory-Hu Tree Is Faster Than Max-Flows
Jason Li, Debmalya Panigrahi
The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting mincuts (and by duality, the values of maxflows) for all pairs of ver…
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
Amir Abboud, Robert Krauthgamer, Jason Li +3
In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all pairs of vertices in an undirected graph can be solved using on…
Deterministic Min-cut in Poly-logarithmic Max-flows
Jason Li, Debmalya Panigrahi
We give a deterministic algorithm for finding the minimum (weight) cut of an undirected graph on vertices and edges using calls to any maximum flow subr…
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
We give an -time algorithm for finding - min-cuts for all pairs of vertices and in a simple, undirected graph on vertices. We do so by constructing a…
Universal Algorithms for Clustering Problems
Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi
This paper presents universal algorithms for clustering problems, including the widely studied -median, -means, and -center objectives. The input is a metric space contain…
Minimum Cuts in Directed Graphs via Max-Flows
Ruoxu Cen, Jason Li, Danupon Nanongkai +2
We give an algorithm to find a mincut in an -vertex, -edge weighted directed graph using calls to any maxflow subroutine. Using state of the art maxflow…
Vertex Connectivity in Poly-logarithmic Max-flows
Jason Li, Danupon Nanongkai, Debmalya Panigrahi +2
The vertex connectivity of an -edge -vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In thi…