NP-completeness of the linear complementarity problem
type: Item
instance of: scholarly article
title: NP-completeness of the linear complementarity problem
zbMATH Open document ID: 0632.90072
DOI: 10.1007/BF00940344
author: B. George
published in: Journal of Optimization Theory and Applications
publication date: 1989-01-01T00:00:00Z
review text: We consider the linear complementarity problem (q,M) for which the data is the integer column vector \(q\in R^ n\) and the integer square matrix M of order n. GLCP is the decision problem: Does (q,M) have a solution? We show that GLCP is NP-complete in the strong sense.
Mathematics Subject Classification ID: 90C33
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 4029285
zbMATH Keywords: NP-completeness in the strong sense
zbMATH Keywords: 0-1 knapsack problems
zbMATH Keywords: linear complementarity
MaRDI profile type: Publication
cites work: Q4101610
cites work: Computational complexity of LCPs associated with positive definite symmetric matrices
cites work: Computational complexity of complementary pivot methods
cites work: Q4198056
cites work: `` Strong '' NP-Completeness Results
full work available at URL: https://doi.org/10.1007/bf00940344
OpenAlex ID: W2015893008
description: scientific article; zbMATH DE number 4029285