Sparse linear complementarity problems

Hanna Sumita; Naonori Kakimura; Kazuhisa Makino

doi:10.1007/978-3-642-38233-8_30

Sparse linear complementarity problems

Hanna Sumita, Naonori Kakimura, Kazuhisa Makino

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

Abstract

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(n³ 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 language	English
Title of host publication	Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings
Pages	358-369
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-38233-8_30
Publication status	Published - 2013 Sept 9
Externally published	Yes
Event	8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Spain Duration: 2013 May 22 → 2013 May 24

Publication series

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

Other

Other	8th International Conference on Algorithms and Complexity, CIAC 2013
Country/Territory	Spain
City	Barcelona
Period	13/5/22 → 13/5/24

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-38233-8_30

Cite this

Sumita, H., Kakimura, N., & Makino, K. (2013). Sparse linear complementarity problems. In Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings (pp. 358-369). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7878 LNCS). https://doi.org/10.1007/978-3-642-38233-8_30

Sparse linear complementarity problems. / Sumita, Hanna; Kakimura, Naonori; Makino, Kazuhisa.
Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. p. 358-369 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7878 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sumita, H, Kakimura, N & Makino, K 2013, Sparse linear complementarity problems. in Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7878 LNCS, pp. 358-369, 8th International Conference on Algorithms and Complexity, CIAC 2013, Barcelona, Spain, 13/5/22. https://doi.org/10.1007/978-3-642-38233-8_30

@inproceedings{77c35ff5070d42fca0d3a05ef0a237d7,

title = "Sparse linear complementarity problems",

abstract = "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.",

author = "Hanna Sumita and Naonori Kakimura and Kazuhisa Makino",

year = "2013",

month = sep,

day = "9",

doi = "10.1007/978-3-642-38233-8_30",

language = "English",

isbn = "9783642382321",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "358--369",

booktitle = "Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings",

note = "8th International Conference on Algorithms and Complexity, CIAC 2013 ; Conference date: 22-05-2013 Through 24-05-2013",

}

TY - GEN

T1 - Sparse linear complementarity problems

AU - Sumita, Hanna

AU - Kakimura, Naonori

AU - Makino, Kazuhisa

PY - 2013/9/9

Y1 - 2013/9/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84883351739&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883351739&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38233-8_30

DO - 10.1007/978-3-642-38233-8_30

M3 - Conference contribution

AN - SCOPUS:84883351739

SN - 9783642382321

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 358

EP - 369

BT - Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings

T2 - 8th International Conference on Algorithms and Complexity, CIAC 2013

Y2 - 22 May 2013 through 24 May 2013

ER -

Sparse linear complementarity problems

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this