Showing cs.DSShow all
3 papers · 1 filter
cs.DS2023
Fast Algorithms for Separable Linear Programs
Sally Dong, Gramoz Goranci, Lawrence Li +2
In numerical linear algebra, considerable effort has been devoted to obtaining faster algorithms for linear systems whose underlying matrices exhibit structural properties. A promi…
cs.DS2023
Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
Sally Dong, Guanghao Ye
We present an algorithm for min-cost flow in graphs with vertices and edges, given a tree decomposition of width and size , and polynomially bounded, integral edge c…
cs.DS2022
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
Sally Dong, Yu Gao, Gramoz Goranci +4
We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm fo…