Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard

DOI10.1007/S101070050087MaRDI QIDQ1806034zbMATH OpenOpenAlexFDO

Authors Levent Tunçel

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

zbMATH Keywords

computational complexitycomplexity measureprimal-dual interior-point algorithmprimal-dual of linear programming

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Computing the norm ∥A∥∞,1 is NP-hard^∗
• On the complexity of approximating extremal determinants in matrices
• Computational complexity of norm-maximization
• Matrix \(p\)-norms are NP-hard to approximate if \(p\neq1,2,\infty\)

Cited in

(6)

• On circuit diameter bounds via circuit imbalances
• Extreme points of well-posed polytopes
• 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
• On circuit diameter bounds via circuit imbalances
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• On the complexity of approximating extremal determinants in matrices

This page was built for publication: Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1806034)