A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem
From MaRDI portal
Publication:1939694
DOI10.1016/J.ORL.2012.08.013zbMATH Open1258.90082arXiv1112.0217OpenAlexW2150230989MaRDI QIDQ1939694FDOQ1939694
Publication date: 5 March 2013
Published in: Operations Research Letters (Search for Journal in Brave)
Abstract: We give a polynomial-time dynamic programming algorithm for solving the linear complementarity problem with tridiagonal or, more generally, Hessenberg P-matrices. We briefly review three known tractable matrix classes and show that none of them contains all tridiagonal P-matrices.
Full work available at URL: https://arxiv.org/abs/1112.0217
dynamic programmingtridiagonal matrixpolynomial-time algorithmHessenberg matrixlinear complementarityP-matrix
Cites Work
- Title not available (Why is that?)
- On the complexity of the parity argument and other inefficient proofs of existence
- Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
- A Partition Theorem for Euclidean n-Space
- NP-completeness of the linear complementarity problem
- Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
- Linear complementarity problems solvable by A single linear program
- Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
- Minkowski matrices.
- On the solution of large, structured linear complementarity problems: The tridiagonal case
Cited In (3)
This page was built for publication: A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1939694)
