EP theorems and linear complementarity problems

DOI10.1016/S0166-218X(97)00143-1zbMath0908.90251MaRDI QIDQ1392569

Makoto Namiki, Komei Fukuda, Akihisa Tamura

Publication date: 18 March 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

linear complementarityexistentially polynomial time

Mathematics Subject Classification ID

Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation, Pivoting in linear complementarity: Two polynomial-time cases, Criss-cross methods: A fresh view on pivot algorithms, Exterior point simplex-type algorithms for linear and network optimization problems, The s-monotone index selection rule for criss-cross algorithms of linear complementarity problems, A polynomial path-following interior point algorithm for general linear complementarity problems, Polynomial convergence of two higher order interior-point methods for \(P_*(\kappa)\)-LCP in a wide neighborhood of the central path, EP theorem for dual linear complementarity problems, Feasible Corrector-Predictor Interior-Point Algorithm for $P_{*} (\kappa)$-Linear Complementarity Problems Based on a New Search Direction, New criss-cross type algorithms for linear complementarity problems with sufficient matrices, Predictor-corrector interior-point algorithm for \(P_*(\kappa)\)-linear complementarity problems based on a new type of algebraic equivalent transformation technique

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The principal pivoting method revisited
• NP-completeness of the linear complementarity problem
• Sufficient matrices and the linear complementarity problem
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• The linear complementarity problem, sufficient matrices, and the criss- cross method
• Manifestations of the Schur complement
• \(P_ *\)-matrices are just sufficient
• Complementary pivot theory of mathematical programming
• The Existence of a Short Sequence of Admissible Pivots to an Optimal Basis in LP and LCP
• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• Equilibrium Points of Bimatrix Games
• Bimatrix Equilibrium Points and Mathematical Programming
• Direct Methods for Solving Symmetric Indefinite Systems of Linear Equations