Sparse linear complementarity problems

Hanna Sumita, Naonori Kakimura, Kazuhisa Makino

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


In this paper, we study the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrix has at most k nonzero entries per row. It is known that 1-LCP is solvable in linear time, while 3-LCP is strongly NP-hard. We show that 2-LCP is strongly NP-hard, while it can be solved in O(n3 logn) time if it is sign-balanced, i.e., each row has at most one positive and one negative entries, where n is the number of constraints. Our second result matches with the currently best known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.

Original languageEnglish
Title of host publicationAlgorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings
Number of pages12
Publication statusPublished - 2013 Sept 9
Externally publishedYes
Event8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Spain
Duration: 2013 May 222013 May 24

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7878 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th International Conference on Algorithms and Complexity, CIAC 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Sparse linear complementarity problems'. Together they form a unique fingerprint.

Cite this