Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


An Output-Sensitive Algorithm for Multi-Parametric LCPs with Sufficient Matrices


K. Fukuda, C.N. Jones, Sebastiano Columbano

CRM Proceedings and Lecture Notes, vol. 48

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 nondegenerate. We give a lexicographic perturbation technique to resolve degeneracy as well. Unlike for the nonparametric case, the resolution turns out to be nontrivial, and in particular, it involves linear programming (LP) duality and multi-objective LP.


Type of Publication:


M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { FukJon:2009:IFA_3196,
    author={K. Fukuda and C.N. Jones and Sebastiano Columbano},
    title={{An Output-Sensitive Algorithm for Multi-Parametric LCPs
	  with Sufficient Matrices}},
    journal={CRM Proceedings and Lecture Notes},
Permanent link