Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
summary
Presents a 1+ε fractional LP solver for kECSS that runs in near-linear time Õ(m/ε²) and converts to a (2+ε)-approximation for integral k-edge-connected spanning subgraphs in Õ(m/ε² + k² n^{1.5}/ε²) time, improving over O(m n k) and O(n²) prior algorithms. Key technical steps: handle the LP’s box constraints via knapsack-cover strengthening, reduce the resulting normalized free cut MinRow oracle to polylog many standard mincuts, and maintain these under multiplicative-weight updates.
AI-written summary · about