5 papers · 1 filter
Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
Yang P. Liu, Richard Peng, Colin Tang +2
Consider the empirical risk minimization (ERM) problem, which is stated as follows. Let be compact convex sets with for $i \in [m…
Approximate Spanning Tree Counting from Uncorrelated Edge Sets
Yang P. Liu, Richard Peng, Junzhao Yang
We show an time algorithm that on a graph with edges and vertices outputs its spanning tree count up to a multiplicative factor with…
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
Jan van den Brand, Li Chen, Rasmus Kyng +5
We provide an algorithm which, with high probability, maintains a -approximate maximum flow on an undirected graph undergoing -edge additions in amortized $m^{o(1)} ε^{-3…
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
Jan van den Brand, Li Chen, Rasmus Kyng +5
We give a deterministic time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral dem…
-norm Flow Diffusion in Near-Linear Time
Li Chen, Richard Peng, Di Wang
Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervi…