Document Open Access Logo

Parameterized Complexity of Sparse Linear Complementarity Problems

Authors Hanna Sumita, Naonori Kakimura, Kazuhisa Makino

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.355.pdf
  • Filesize: 465 kB
  • 10 pages

Document Identifiers

Author Details

Hanna Sumita
Naonori Kakimura
Kazuhisa Makino

Cite As Get BibTex

Hanna Sumita, Naonori Kakimura, and Kazuhisa Makino. Parameterized Complexity of Sparse Linear Complementarity Problems. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 355-364, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.355

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 all the parameters. We also show that if we drop any of the three parameters, then the LCP is fixed-parameter intractable.
In addition, we discuss the nonexistence of a polynomial kernel for the LCP.

Subject Classification

Keywords
  • linear complementarity problem
  • sparsity
  • parameterized complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. V. Arvind, J. Köbler, S. Kuhnert, and J.Torán. Solving linear equations parameterized by Hamming weight. In Proceedings of the 9th International Symposium on Parameterized and Exact Computation, pages 39-50, 2014. Google Scholar
  2. H. Björklund, O. Svensson, and S. Vorobyov. Linear complementarity algorithms for mean payoff games. Technical Report 2005-05, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, 2005. Google Scholar
  3. H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences, 75:423-434, 2009. Google Scholar
  4. X. Chen, X. Deng, and S. Teng. Sparse games are hard. In Proceedings of the 2nd International Workshop on Internet and Network Economics, pages 262-273, 2006. Google Scholar
  5. X. Chen, X. Deng, and S. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56:14:1-14:57, 2009. Google Scholar
  6. S. J. Chung. NP-completeness of the linear complementarity problem. Journal of Optimization Theory and Applications, 60:393-399, 1989. Google Scholar
  7. B. Codenotti, M. Leoncini, and G. Resta. Efficient computation of Nash equilibria for very sparse win-lose bimatrix games. In Proceedings of the 14th Annual European Symposium on Algorithms, pages 232-243, 2006. Google Scholar
  8. E. Cohen and N. Megiddo. Improved algorithms for linear inequalities with two variables per inequality. SIAM Journal on Computing, 23:1313-1347, 1994. Google Scholar
  9. R. W. Cottle. The principal pivoting method of quadratic programming. In Mathematics of Decision Sciences, Part 1, pages 142-162. American Mathematical Society, Providence R. I., 1968. Google Scholar
  10. R. W. Cottle and G. B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and Its Applications, 1:103-125, 1968. Google Scholar
  11. R. W. Cottle, J. S. Pang, and R. E. Stone. The Linear Complementarity Problem. Academic Press, Boston, 1992. Google Scholar
  12. P. Damaschke. Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing. Theoretical Computer Science, 511:137-146, 2013. Google Scholar
  13. C. Daskalakis and C. H. Papadimitriou. On oblivious PTAS’s for Nash equilibrium. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 75-84, 2009. Google Scholar
  14. R. G. Downey and M. R. Fellows. Fixed-parameter intractability. In Proceedings of the 7th Annual Structure in Complexity Theory Conference, pages 36-49, 1992. Google Scholar
  15. R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, New York, 1999. Google Scholar
  16. V. Estivill-Castro and M. Parsa. Computing Nash equilibria gets harder: new results show hardness even for parameterized complexity. In Proceedings of the 15th Australasian Symposium on Computing, pages 83-90, 2009. Google Scholar
  17. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Berlin, 2006. Google Scholar
  18. I. Gilboa and E. Zemel. Nash and correlated equilibria: some complexity considerations. Games and Economic Behavior, 1:80-93, 1989. Google Scholar
  19. D. Hermelin, C. Huang, S. Kratsch, and M. Wahlström. Parameterized two-player Nash equilibrium. Algorithmica, 65:1-15, 2013. Google Scholar
  20. D. S. Hochbaum and J. Naor. Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM Journal on Computing, 23:1179-1192, 1994. Google Scholar
  21. S. Kratsch. On polynomial kernels for integer linear programs: covering, packing and feasibility. In Proceedings of the 21st Annual European Symposium, pages 647-658, 2013. Google Scholar
  22. S. Kratsch. On polynomial kernels for sparse integer linear programs. In Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science, pages 80-91, 2013. Google Scholar
  23. S. Kratsch and V. A. Quyen. On kernels for covering and packing ILPs with small coefficients. In Proceedings of the 9th International Symposium on Parameterized and Exact Computation, pages 307-318, 2014. Google Scholar
  24. C. E. Lemke. Bimatrix equilibrium points and mathematical programming. Management Science, 11:681-689, 1965. Google Scholar
  25. K. G. Murty. Linear Complementarity, Linear and Nonlinear Programming. Internet Edition, 1997. Google Scholar
  26. T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pages 216-226, 1978. Google Scholar
  27. H. Sumita, N. Kakimura, and K. Makino. The linear complementarity problems with a few variables per constraint. Mathematics of Operations Research, to appear. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact