Randomized pivot algorithms for \(P\)-matrix linear complementarity problems

DOI10.1007/s101070100268zbMath1012.68225OpenAlexW1994867648MaRDI QIDQ1611006

Walter D. jun. Morris

Publication date: 20 August 2002

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

Full work available at URL: https://doi.org/10.1007/s101070100268

zbMATH Keywords

\(P\)-matrixRANDOM-EDGE

Mathematics Subject Classification ID

Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Randomized algorithms (68W20) Extreme-point and pivoting methods (90C49)

Related Items

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations ⋮ Pivoting in linear complementarity: Two polynomial-time cases ⋮ A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem ⋮ Unique end of potential line ⋮ Realizability makes a difference: a complexity gap for sink-finding in USOs ⋮ Counting unique-sink orientations ⋮ Recent development in computational complexity characterization of Nash equilibrium ⋮ Enumeration of PLCP-orientations of the 4-cube ⋮ Violator spaces: Structure and algorithms ⋮ Cyclic games and linear programming ⋮ Random edge can be exponential on abstract cubes ⋮ Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a \(P\)-matrix ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Unique End of Potential Line