Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs
summary
Claims a concrete speedup: a strongly polynomial interior‑point method breaks the quadratic gap between high‑accuracy and exact solvers for combinatorial LP, cutting the previous m^{ω+2}·log κ dependence down to roughly m^{ω+1}·log κ in the real‑RAM model. It achieves this by a refined layered least‑squares predictor, larger step sizes, finer layering + stronger convergence lemmas, and block‑almost‑orthogonal row decompositions with dynamic matrix updates; the algorithm is deterministic and the analysis yields the stated iteration and runtime bounds.
AI-written summary · about