2025/03/25 by Objois, Étienne, Vladu, Adrian
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2503.19553
We provide the first nearly-linear time algorithm for approximating ℓq → p-norms of non-negative matrices, for q ≥ p ≥ 1. Our algorithm returns a (1-ε)-approximation to the matrix norm in time \widetildeO((1)/(q ε) ⋅ nnz(\boldsymbolA)), where \boldsymbolA is the input matrix, and improves upon the previous state of the art, which either proved convergence only in the limit [Boyd '74], or had very high polynomial running times [Bhaskara-Vijayraghavan, SODA '11]. Our algorithm is extremely simple, and is largely inspired from the coordinate-scaling approach used for positive linear program solvers. We note that our algorithm can readily be used in the [Englert-Räcke, FOCS '09] to improve the running time of constructing O(log n)-competitive ℓp-oblivious routings. We thus complement this result with a simple cutting-plane based scheme for computing optimal oblivious routings in graphs with respect to any monotone norm. Combined with state of the art cutting-plane solvers, this scheme runs in time \widetildeO(n6 m3), which is significantly faster than the one based on Englert-Räcke, and generalizes the ℓ_∞ routing algorithm of [Azar-Cohen-Fiat-Kaplan-Räcke, STOC '03].