The Linear Complementarity Problems with a Few Variables per Constraint

In this paper, we consider the sparse linear complementarity problem, denoted by k -LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2015-11, Vol.40 (4), p.1015-1026
Main Authors: Sumita, Hanna, Kakimura, Naonori, Makino, Kazuhisa
Format: Article
Language:English
Subjects:
Analysis
combinatorial algorithm
Linear complementarity problem
Linear programming
Mathematical problems
Matrix
NP-hardness
polynomial solvability
Polynomials
Studies
two-variable constraints
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider the sparse linear complementarity problem, denoted by k -LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.2014.0708