research
∙
10/13/2022
Online Algorithms for the Santa Claus Problem
The Santa Claus problem is a fundamental problem in fair division: the g...
share
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
∙
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
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
∙
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
∙
06/02/2020
