EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1276. The size of the handicap
Invited abstract in session MB-38: Interior point methods, stream Conic Optimization: Theory, Algorithms, and Applications.
Monday, 10:30-12:00Room: 34 (building: 306)
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 handicap is a matrix parameter associated with the linear complementarity problem (LCP). While LCP is an NP-hard problem, there are special cases, such as when the handicap of its coefficient matrix is finite, where an interior point algorithm can efficiently solve the problem. However, the theoretical complexity of the algorithm is linearly dependent on the handicap. Consequently, a key and relevant inquiry is to give an upper bound on the size of the handicap. We show that, with a fixed matrix dimension, the handicap cannot be arbitrarily large, more precisely, we prove the conjecture that it cannot be double exponential in the bit size of the matrix.
Keywords
- Continuous Optimization
- Mathematical Programming
- Programming, Linear
Status: accepted
Back to the list of papers