401-3050-65L Student Seminar in Combinatorics: Linear Complementarity
Semester | Autumn Semester 2015 |
Lecturers | K. Fukuda |
Periodicity | yearly recurring course |
Language of instruction | English |
Comment | Number of participants limited to 18. |
Abstract | We study the combinatorics and the complexity of various subclasses of the linear complementarity problem. |
Objective | To understand the importance of linear complementarity as a common generalization of linear programming, bimatrix games and convex quadratic programming. |
Content | 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. |
Literature | To 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 . |
Prerequisites / Notice | Basic knowlege of linear programming. |