高级检索
This two-part talk will survey recent developments in optimization algorithms and data structures for computing network flows. Flows, or combinations of paths, have origins in routing and assignment problems, and are closely related to many core primitives in data science. Previously, even for finding the maximum of edge-disjoint s-t paths, the best running time bound was at least m^{4/3}. A combination of these new tools on the other hand led to an algorithm for optimizing a flow to minimize general edge-separable convex functions whose asymptotic running time is almost-linear in the graph size. The first half of the talk will overview approaches for computing network flows, then discuss the connections with continuous optimization and graph approximation theory critical for overcoming bottlenecks facing purely combinatorial methods. The second half of the talk will discuss recent developments of speeding up second order optimization methods using dynamic graph data structures, with focus on tree compression and divide-and-conquer schemes critical for fast maintenance of edge-sparsifiers and vertex eliminations.
网络流算法
彭泱