文章基本信息

标题：Parameterized Complexity of Sparse Linear Complementarity Problems
本地全文：下载
作者：Hanna Sumita ; Naonori Kakimura ; Kazuhisa Makino 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：43
页码：355-364
DOI：10.4230/LIPIcs.IPEC.2015.355
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：linear complementarity problem; sparsity; parameterized complexity