We give an algorithm that computes exact maximum flows and minimum-cost flows on
directed graphs with m edges and polynomially bounded integral demands, costs, and …

We give a deterministic m^1+o(1) time algorithm that computes exact maximum flows and
minimum-cost flows on directed graphs with m edges and polynomially bounded integral …

In this paper we provide new randomized algorithms with improved runtimes for solving
linear programs with two-sided constraints. In the special case of the minimum cost flow …

The fastest known LP solver for general (dense) linear programs is due to [Cohen, Lee and
Song'19] and runs in O*(n ω+ n 2.5− α/2+ n 2+ 1/6) time. A number of follow-up works [Lee …

In the single-source shortest paths problem, the goal is to compute the shortest path tree
from a designated source vertex in a weighted, directed graph. We present the first near …

Maximum bipartite matching (MBM) is a fundamental problem in combinatorial optimization
with a long and rich history. A classic result of Hopcroft and Karp (1973) provides an O (m√ …

We give an algorithm for computing exact maximum flows on graphs with edges and integer
capacities in the range in time. We use to suppress logarithmic factors in. For sparse graphs …

Recent advances by practitioners in the deep learning community have breathed new life
into Locality Sensitive Hashing (LSH), using it to reduce memory and time bottlenecks in …

Vizing's celebrated theorem states that every simple graph with maximum degree Δ admits a
(Δ+ 1) edge coloring which can be found in O (m· n) time on n-vertex m-edge graphs. This is …

We present an algorithm which given any m-edge directed graph with positive integer
capacities at most U, vertices a and b, and an approximation parameter ϵ∈(0,1) computes …