401-3050-65L  Student Seminar in Combinatorics: Linear Complementarity

SemesterHerbstsemester 2015
DozierendeK. Fukuda
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheEnglisch
KommentarMaximale Teilnehmerzahl: 18


KurzbeschreibungWe study the combinatorics and the complexity of various subclasses of the linear complementarity problem.
LernzielTo understand the importance of linear complementarity as a common generalization of linear programming, bimatrix games and
convex quadratic programming.
InhaltThe 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.
LiteraturTo be posted here before the first class on September 15.

The seminar schedule and a list of articles:
Link
(Version October 7, 2015). Please check the version date, as it gets updated frequently.

Accepted Reports:
Link


The slides of the overview (Revised on September 22, 2015):
Link .
Voraussetzungen / BesonderesBasic knowlege of linear programming.