Rudiments of an average case complexity theory for piecewise-linear path following algorithms

DOI10.1007/BF01580727zbMath0657.90089MaRDI QIDQ1111475

James Renegar

Publication date: 1988

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

homotopy algorithmspiecewise linear approximationssimplicial triangulationaverage directional densitypiecewise-linear path following algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Numerical computation of solutions to systems of equations (65H10)

Related Items (2)

On parametric nonlinear programming ⋮ A class of ``onto multifunctions

Uses Software

• PLALGO

Cites Work

• Computational complexity of a piecewise linear homotopy algorithm
• On the cost of computing roots of polynomials
• Equivalence of Surface Density and Average Directional Density
• On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials
• On the cost of approximating all roots of a complex polynomial
• On triangulations for computing fixed points
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• On the computational complexity of piecewise-linear homotopy algorithms

This page was built for publication: Rudiments of an average case complexity theory for piecewise-linear path following algorithms