Some LCPs solvable in strongly polynomial time with Lemke's algorithm

• 成果类型: Article
• 署名作者: Adler, Ilan; Cottle, Richard W.; Pang, Jong-Shi
• 署名单位: University of California System; University of California Berkeley; Stanford University; University of Southern California
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-0996-4
• 发表日期: 2016
• 页码: 477-493
• 关键词: linear complementarity-problems; computational complexity; matrices

摘要

We identify a class of Linear Complementarity Problems (LCPs) that are solvable in strongly polynomial time by Lemke's Algorithm (Scheme 1) or by the Parametric Principal Pivoting Method (PPPM). This algorithmic feature for the class of problems under consideration here is attributable to the proper selection of the covering vector in Scheme 1 or the parametric direction vector in the PPPM which leads to solutions of limited and monotonically increasing support size; such solutions are sparse. These and other LCPs may very well have multiple solutions, many of which are unattainable by either algorithm and thus are said to be elusive. The initial conditions imposed on the new matrix class identified in Sect. 2 are subsequently relaxed in later sections.