401-3050-65L Student Seminar in Combinatorics: Linear Complementarity
|Periodizität||jährlich wiederkehrende Veranstaltung|
|Kommentar||Maximale Teilnehmerzahl: 18|
|Kurzbeschreibung||We study the combinatorics and the complexity of various subclasses of the linear complementarity problem.|
|Lernziel||To understand the importance of linear complementarity as a common generalization of linear programming, bimatrix games and|
convex quadratic programming.
|Inhalt||The Linear Complementarity Problem (LCP) was introduced in mid 1960's (1965-67) by Lemke and Cottle-Dantzig|
as a common generalization of linear programming, bimatrix game and convex quadratic programming.
The problem is NP-hard in general, but there are many subclasses of LCP that are in P (polynomially solvable)
or suspected to be in P. The reason for the possible polynomially solvability is that these studied
subclasses (e.g. P-matrix LCPs and positive-definite LCPs) can be formulated as a problem which
admits a solution that has a succinct certificate for its correctness. Moreover, there are elegant
combinatorial abstractions of these subclasses.
In this seminar, we study the most important papers/books, both old and new, in the theory of LCP, and
aim at understanding what is crucial lack of knowledge in proving or disproving existing conjectures.
|Literatur||To be posted here before the first class on September 15.|
The seminar schedule and a list of articles:
(Version October 7, 2015). Please check the version date, as it gets updated frequently.
The slides of the overview (Revised on September 22, 2015):
|Voraussetzungen / Besonderes||Basic knowlege of linear programming.|