On the complexity of computing the handicap of a sufficient matrix |
| |
Authors: | Etienne de Klerk Marianna E -Nagy |
| |
Institution: | (3) Dept. Comput. & Software McMaster Univ., 1280 Main Street West, Hamilton, Ontario, Canada, L8S 4L7 |
| |
Abstract: | The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point
methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In
this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity
bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite
programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|