 |
Universität Augsburg
|
|
|
Universität Augsburg
|
|
Professor Dr. Ralf Werner
Universität Augsburg
spricht am
Dienstag, 17. Januar 2017
um
16:00 Uhr
im
Raum 1005 (L1)
über das Thema:
| Abstract: |
| Nach einer kurzen Einführung in Bernoulli-Matrizen widmet sich der Hauptteil des Vortrags der Fragestellung, wie gegebene Matrizen effizient auf die Bernoulli-Eigenschaft geprüft werden können. Es wird sich zeigen, daß ein effizienter Zugang auf einer spezifischen Spaltengenerierungsmethode beruht. Numerische Resultate zeigen, daß dieser Zugang es erlaubt, die Dimension für Anwendungen von d = 20 auf d = 40 zu verdoppeln. Anschließend wird gezeigt, daß sich jedes binäre quadratische Optimierungsproblem als lineares Problem über dem Bernoulli-Polytop schreiben läßt. Einerseits zeigt dies, daß das Testen der Bernoulli-Eigenschaft NP-schwer ist. Andererseits erlaubt dies neue effiziente Heuristiken für obere und untere Schranken für binäre quadratische Optimierungsprobleme. |
| Hierzu ergeht herzliche Einladung. |