The Linear Complementarity Problems with a Few Variables per Constraint

• 成果类型: Article
• 署名作者: Sumita, Hanna; Kakimura, Naonori; Makino, Kazuhisa
• 署名单位: University of Tokyo; University of Tokyo; Kyoto University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0708
• 发表日期: 2015
• 页码: 1015-1026
• 关键词: integer programs; solving systems; INEQUALITY; algorithms; equilibrium; complexity

摘要

In this paper, we consider the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i. e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.