Dynamic Matrix Algorithms and Applications in Convex and Combinatorial Optimization

Dynamic algorithms are used to efficiently maintain solutions to problems where the input undergoes some changes.This thesis studies dynamic algorithms that maintain solutions to linear algebra problems and we explore their applications and implications for dynamic graphs and optimization problems. Dynamic graph algorithms maintain properties of changing graphs, such as the distances in a graph that undergoes edge deletions and insertions.The main question is how to maintain the information without recomputing the solution from scratch whenever the graph changes.If maintaining the information without trivial recomputation is possible, the next natural question is how quickly the information can be maintained.This thesis makes progress on both questions: (i) We construct the first non-trivial fully dynamic graph algorithms for single-source shortest paths, diameter and other problems. This answers open questions stated in, e.g., [Demetrescu-Italiano'04]. (ii) We obtain matching upper and conditional lower bounds for the complexity of maintaining reachability, maximum matching, directed cycle detection and many other graph properties. This settles the complexity for these problems and answers an open problem stated in [Abboud-V.Williams'14]. We get these results by reducing the dynamic graph problems to dynamic linear algebra problems for which we develop new algorithms. At the same time, conditional lower bounds for the dynamic graph problems thus imply lower bounds for dynamic linear algebra problems as well. We apply the developed techniques for dynamic linear algebra to algorithms for linear programs and obtain optimal (i.e. nearly-linear time) algorithms for dense instances of linear programs, Markov decision processes, linear L1 regression, and graph specific special cases thereof such as bipartite matching, minimum-cost flow, and (negative weight) shortest paths.For bipartite matching on dense graphs, this is the first improvement since the classic algorithms by [Dinic'70;Hopcroft-Karp'71;Karzanov'73;Ibarra-Moran'81]. The results are obtained by using that algorithms (i.e. interior point methods) for these problems are iterative and must repeatedly solve linear systems and other linear algebra problems. By using techniques from dynamic linear algebra (i.e. dynamic matrix algorithms), we are able to maintain the solution to these subproblems, reducing the time required per iteration.The construction of our algorithms relies on a joint analysis of the iterative algorithm and the dynamic matrix algorithms.On one hand, we develop robust interior point methods which are able to handle relaxations and approximations to the linear algebra subroutines.On other hand, we develop fast dynamic matrix algorithms that are able to maintain the solution to these relaxed subproblems efficiently.QC 20210525