401-3050-65L Student Seminar in Combinatorics: Linear Complementarity
Semester | Herbstsemester 2015 |
Dozierende | K. Fukuda |
Periodizität | jährlich wiederkehrende Veranstaltung |
Lehrsprache | Englisch |
Kommentar | Maximale Teilnehmerzahl: 18 |
Lehrveranstaltungen
Nummer | Titel | Umfang | Dozierende | ||||
---|---|---|---|---|---|---|---|
401-3050-00 S | Student Seminar in Combinatorics: Linear Complementarity | 2 Std. |
| K. Fukuda |
Katalogdaten
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: 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 / Besonderes | Basic knowlege of linear programming. |
Leistungskontrolle
Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird) | |
Leistungskontrolle als Semesterkurs | |
ECTS Kreditpunkte | 4 KP |
Prüfende | K. Fukuda |
Form | unbenotete Semesterleistung |
Prüfungssprache | Englisch |
Repetition | Repetition nur nach erneuter Belegung der Lerneinheit möglich. |
Lernmaterialien
Keine öffentlichen Lernmaterialien verfügbar. | |
Es werden nur die öffentlichen Lernmaterialien aufgeführt. |
Gruppen
Keine Informationen zu Gruppen vorhanden. |
Einschränkungen
Plätze | Maximal 18 |
Vorrang | Die Belegung der Lerneinheit ist nur durch die primäre Zielgruppe möglich |
Primäre Zielgruppe | Mathematik BSc (404000)
ab Semester 05 Mathematik MSc (437000) Angewandte Mathematik MSc (437100) Mathematik (Mobilität) (448000) |
Warteliste | Bis 28.09.2015 |
Angeboten in
Studiengang | Bereich | Typ | |
---|---|---|---|
Mathematik Bachelor | Seminare | W | |
Mathematik Master | Seminare | W |