A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem

DOI10.1016/j.orl.2012.08.013zbMath1258.90082arXiv1112.0217OpenAlexW2150230989MaRDI QIDQ1939694

Markus Sprecher, Bernd Gärtner

Publication date: 5 March 2013

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.0217

zbMATH Keywords

linear complementaritydynamic programmingpolynomial-time algorithmtridiagonal matrixP-matrixHessenberg matrix

Mathematics Subject Classification ID

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

Related Items (2)

Counting unique-sink orientations ⋮ SDP relaxation algorithms for \(\mathbf{P(P}_0)\)-tensor detection

Cites Work

• Unnamed Item
• NP-completeness of the linear complementarity problem
• On the solution of large, structured linear complementarity problems: The tridiagonal case
• On the complexity of the parity argument and other inefficient proofs of existence
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• Minkowski matrices.
• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• Linear complementarity problems solvable by A single linear program
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• A Partition Theorem for Euclidean n-Space

This page was built for publication: A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem