56. Bounding the handicap of a matrix
Invited abstract in session WF-3: Interior-Point Methods for Linear Complementarity Problems II, stream Advances in theory and practice of interior-point methods.
Wednesday, 16:45 - 18:15Room: C 104
Authors (first author is the speaker)
| 1. | Marianna E.-Nagy
|
| Corvinus University of Budapest | |
| 2. | Tibor Illés
|
| Corvinus University of Budapest | |
| 3. | Laszlo Vegh
|
| Mathematics, LSE |
Abstract
The linear complementarity problem (LCP), without any assumption on its coefficient matrix, is NP-hard. However, in special cases, for example, when the matrix is sufficient, the LCP is solvable efficiently. In this case, an interior point algorithm can provide a solution in polynomial time. Nevertheless, the method's theoretical complexity is directly tied to a matrix parameter known as the "handicap." Therefore an important question to address is the possible magnitude of the handicap. It is known that the handicap of a sufficient matrix is finite, but it can be exponential in the dimension of the matrix. We demonstrate that, with a fixed matrix dimension, the handicap cannot be arbitrarily large, specifically, we prove the conjecture that it cannot be double exponential in the bit size of the matrix.
Keywords
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers