Name
Abstract | ||
|---|---|---|
In this paper, we study the parameterized complexity of the linear complementarity problem (LCP), which is one of the most fundamental mathematical optimization problems. The parameters we focus on are the sparsities of the input and the output of the LCP: the maximum numbers of nonzero entries per row/column in the coefficient matrix and the number of nonzero entries in a solution. Our main result is to present a fixed-parameter algorithm for the LCP with the combined parameter. We also show that if we drop any of the three parameters, then the LCP is NP-hard or W[1]-hard. In addition, we show the nonexistence of a polynomial kernel for the LCP unless coNP $$\\subseteq $$⊆ NP/poly. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00453-016-0229-5 | Algorithmica |
Keywords | DocType | Volume |
Linear complementarity problem,Sparsity,Parameterized complexity | Journal | 79 |
Issue | ISSN | Citations |
1 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hanna Sumita | 1 | 2 | 7.83 |
| Naonori Kakimura | 2 | 59 | 21.18 |
| Kazuhisa Makino | 3 | 1088 | 102.74 |