An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices
| dc.creator | Columbano, Sebastiano | |
| dc.creator | Fukuda, Komei | |
| dc.creator | Jones, Colin | |
| dc.date | 2008-07-15 | |
| dc.date.accessioned | 2026-07-07T09:50:25Z | |
| dc.date.available | 2026-07-07T09:50:25Z | |
| dc.description | This paper considers the multi-parametric linear complementarity problem (pLCP) with sufficient matrices. The main result is an algorithm to find a polyhedral decomposition of the set of feasible parameters and to construct a piecewise affine function that maps each feasible parameter to a solution of the associated LCP in such a way that the function is affine over each cell of the decomposition. The algorithm is output-sensive in the sense that its time complexity is polynomial in the size of the input and linear in the size of the output, when the problem is non-degenerate. We give a lexicographic perturbation technique to resolve degeneracy as well. Unlike for the non-parametric case, the resolution turns out to be nontrivial, and in particular, it involves linear programming (LP) duality and multi-objective LP. | |
| dc.identifier | https://arxiv.org/abs/0807.2318 | |
| dc.identifier | http://arxiv.org/abs/0807.2318 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/164939 | |
| dc.subject | Optimization and Control | |
| dc.subject | 90C33, 90C31 | |
| dc.title | An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices | |
| dc.type | text |