On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming 1: The Predictor–Corrector Algorithm Between N₂(1/4) and N₂(1/2) Attains Precision t in O(√n·t) IterationsResearch Paper
Linear programming asks for the best value of a linear objective subject to linear equations and inequalities. Primal-dual interior-point methods seek feasible primal and dual solutions while keeping every constrained coordinate positive. The resulting pair has a measurable gap between its objective values, so an algorithm can stop when the gap is below a…