2 citations · 3 across the 8 of their papers we have counts for
11 papers
Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
Sayan Bhattacharya, Ruoxu Cen, Debmalya Panigrahi
In (fully) dynamic set cover, the goal is to maintain an approximately optimal solution to a dynamically evolving instance of set cover, where in each step either an element is add…
Fast Algorithms for Graph Arboricity and Related Problems
Ruoxu Cen, Henry Fleischmann, George Z. Li +2
We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in $\sqrt{n} m…
Network Unreliability in Almost-Linear Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
The network unreliability problem asks for the probability that a given undirected graph gets disconnected when every edge independently fails with a given probability . Valiant…
Hypergraph Unreliability in Quasi-Polynomial Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the…
Beyond the Quadratic Time Barrier for Network Unreliability
Ruoxu Cen, William He, Jason Li +1
Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running ti…
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
Ruoxu Cen, William He, Jason Li +1
We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose additio…
Edge Connectivity Augmentation in Near-Linear Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
We give an -time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms…
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…
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…
Sparsification of Directed Graphs via Cut Balance
Ruoxu Cen, Yu Cheng, Debmalya Panigrahi +1
In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the…