Search for: All records

For graphs of average degree $$d$$, positive integer weights bounded by $$W$$, and accuracy parameter $$\epsilon>0$$, [Chazelle, Rubinfeld, Trevisan; SICOMP'05] have shown that the weight of the minimum spanning tree can be $$(1+\epsilon)$$-approximated in $$\tilde{O}(Wd/\epsilon^2)$$ expected time. This algorithm is frequently taught in courses on sublinear time algorithms. However, the $$\tilde{O}(Wd/\epsilon^2)$$-time variant requires an involved analysis, leading to simpler but much slower variations being taught instead. Here we present an alternative that is not only simpler to analyze, but also improves the number of queries, getting closer to the nearly-matching information theoretic lower bound. In addition to estimating the weight of the MST, our algorithm is also a perfect sampler for sampling uniformly at random an edge of the MST. At the core of our result is the insight that halting Prim's algorithm after an expected $$\tilde{O}(d)$$ number of steps, then returning the highest weighted edge of the tree, results in sampling an edge of the MST uniformly at random. Via repeated trials and averaging the results, this immediately implies an algorithm for estimating the weight of the MST. Since our algorithm is based on Prim's, it naturally works for non-integer weighted graphs as well. 

We give the first almost-linear total time algorithm for deciding if a flow of cost at most $$F$$ still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, and cost increases. This implies almost-linear time algorithms for approximating the minimum-cost flow value and s-t distance on such decremental graphs. Our framework additionally allows us to maintain decremental strongly connected components in almost-linear time deterministically. These algorithms also improve over the current best known runtimes for statically computing minimum-cost flow, in both the randomized and deterministic settings. We obtain our algorithms by taking the dual perspective, which yields cut-based algorithms. More precisely, our algorithm computes the flow via a sequence of $$m^{1+o(1)}$$-dynamic min-ratio cut problems, the dual analog of the dynamic min-ratio cycle problem that underlies recent fast algorithms for minimum-cost flow. Our main technical contribution is a new data structure that returns an approximately optimal min-ratio cut in amortized $$m^{o(1)}$$ time by maintaining a tree-cut sparsifier. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [Goranci-Racke-Saranurak-Tan, SODA 2021] that also works in capacitated graphs. All our algorithms are deterministic, though they can be sped up further using randomized techniques while still working against an adaptive adversary. 

Many iterative algorithms in computer science require repeated computation of some algebraic expression whose input varies slightly from one iteration to the next. Although efficient data structures have been proposed for maintaining the solution of such algebraic expressions under low-rank updates, most of these results are only analyzed under exact arithmetic (real-RAM model and finite fields) which may not accurately reflect the more limited complexity guarantees of real computers. In this paper, we analyze the stability and bit complexity of such data structures for expressions that involve the inversion, multiplication, addition, and subtraction of matrices under the word-RAM model. We show that the bit complexity only increases linearly in the number of matrix operations in the expression. In addition, we consider the bit complexity of maintaining the determinant of a matrix expression. We show that the required bit complexity depends on the logarithm of the condition number of matrices instead of the logarithm of their determinant. Finally, we discuss rank maintenance and its connections to determinant maintenance. Our results have wide applications ranging from computational geometry (e.g., computing the volume of a polytope) to optimization (e.g., solving linear programs using the simplex algorithm).