An unconditional lower bound for the active-set method on the hypercube

DOI10.1007/978-3-031-93112-3_16MaRDI QIDQ6880136zbMATH OpenFDO

Authors Y. Disser, Nils Mosis

Publication date 22 December 2025

zbMATH Keywords

linear programmingnonlinear programminglower boundsimplex methodactive-set method

Mathematics Subject Classification ID

Linear programming (90C05) Nonlinear programming (90C30) Extreme-point and pivoting methods (90C49)

Cites work

• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• scientific article; zbMATH DE number 1241836 (Why is no real title available?)
• scientific article; zbMATH DE number 1503621 (Why is no real title available?)
• scientific article; zbMATH DE number 3067835 (Why is no real title available?)
• A counterexample to the Hirsch conjecture
• A friendly smoothed analysis of the simplex method
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• A subexponential lower bound for the random facet algorithm for parity games
• A unified worst case for classical simplex and policy iteration pivot rules
• An exponential lower bound for Cunningham's rule
• An exponential lower bound for Zadeh's pivot rule
• An extension of Karmarkar's projective algorithm for convex quadratic programming
• Computational complexity of parametric linear programming
• Exponential lower bounds for many pivot rules for the simplex method
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• Interior point methods are not worse than simplex
• Linear programming and unique sink orientations
• No self-concordant barrier interior point method is strongly polynomial
• Numerical Optimization
• On Simplex Pivoting Rules and Complexity Theory
• Smoothed analysis of algorithms
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• The complexity of the simplex method
• The generalized simplex method for minimizing a linear form under linear inequality restraints
• The simplex algorithm is NP-mighty
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• Upper and lower bounds on the smoothed complexity of the simplex method
• Worst case behavior of the steepest edge simplex method

This page was built for publication: An unconditional lower bound for the active-set method on the hypercube

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