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

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



Lehrveranstaltungen

NummerTitelUmfangDozierende
401-3050-00 SStudent Seminar in Combinatorics: Linear Complementarity2 Std.
Di10:15-12:00HG E 33.3 »
K. Fukuda

Katalogdaten

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.

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
ECTS Kreditpunkte4 KP
PrüfendeK. Fukuda
Formunbenotete Semesterleistung
PrüfungsspracheEnglisch
RepetitionRepetition 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ätzeMaximal 18
VorrangDie Belegung der Lerneinheit ist nur durch die primäre Zielgruppe möglich
Primäre ZielgruppeMathematik BSc (404000) ab Semester 05
Mathematik MSc (437000)
Angewandte Mathematik MSc (437100)
Mathematik (Mobilität) (448000)
WartelisteBis 28.09.2015

Angeboten in

StudiengangBereichTyp
Mathematik BachelorSeminareWInformation
Mathematik MasterSeminareWInformation