A Polynomial-Time Algorithm for the Tridiagonal and Hessenberg P-Matrix\n Linear Complementarity Problem

2011/12/01 by Bernd Gärtner, Gärtner, Bernd, Markus Sprecher +1
Computer Science · Engineering · Mathematics · #65K05 #90C33 #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1112.0217

openalex publication_date 2011/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a polynomial-time dynamic programming algorithm for solving the\nlinear complementarity problem with tridiagonal or, more generally, Hessenberg\nP-matrices. We briefly review three known tractable matrix classes and show\nthat none of them contains all tridiagonal P-matrices.\n

Related

• Enumeration of PLCP-orientations of the 4-cube
• An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices
• Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables
• Fast Solutions to Projective Monotone Linear Complementarity Problems
• New Symbolic Algorithms For Solving A General Bordered Tridiagonal Linear System