Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
From MaRDI portal
Publication:1806034
DOI10.1007/s101070050087zbMath1029.90083OpenAlexW2035532822MaRDI QIDQ1806034
Publication date: 10 February 2004
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s101070050087
computational complexitycomplexity measureprimal-dual interior-point algorithmprimal-dual of linear programming
Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Complexity and performance of numerical algorithms (65Y20)
Related Items
Extreme points of well-posed polytopes ⋮ On circuit diameter bounds via circuit imbalances ⋮ A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
This page was built for publication: Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
