*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 9
Dienstag, 19.09.2000, 16.00–16.20 Uhr, WIL C 133

Gitterbasenreduktion und das Market-Sharing-Problem

Alfred Wassermann, Universität Bayreuth

In „A Class of Hard Small 0-1 Programs“ (LNCS 1412) stellen Cornuéjols und Dawande eine Klasse von Test-Problemen vor, die selbst bei kleinen Problem-Instanzen mit den konventionellen Branch-and-bound- und Branch-and-cut-Methoden extrem schwer zu lösen sind. Erfolgversprechender sind Ansätze, die auf Gitterbasisreduktion zusammen mit vollständiger Aufzählung beruhen. Hier wird der Einsatz einer Methode von Schnorr und Ritter vorgestellt, die die bisherigen Ansätze im Laufzeitverhalten deutlich übertrifft.