Aufgabenstellung

In vielen approximativen Algorithmen muss, um eine gute Approximation zu erhalten, ein Konfigurations LP gelöst werden. Eine Konfiguration kann dabei angeben, welche Items zusammen in einen Bin passen (Bin Packing), welche Jobs auf einer Maschine ausgeführt werden (Scheduling) oder welche Jobs zur gleichen Zeit ausgeführt werden können (Scheduling mit parallelen Tasks). Dieses lineare Programm kann in vielen Fällen nur approximativ gelöst werden, da die Menge der Konfigurationen häufig exponentiell in der Eingabegröße ist. Während des Projektes sollen verschiedene Ansätze dieses LP zu lösen implementiert und miteinander verglichen werden.

Themen

•  Max-Min-Resource-Sharing
  
•  Ellipsoid-Methode nach Grözschel, Lóvasz und Schrijver
  
•  Rucksack Probleme
  
•  Bin- Packing Problem
•  Basis Lösungen
  

Betreuer

Klaus Jansen und Malin Rau

Organisatorisches

Vorbesprechung:  Freitag 30. 10. 2015, 11:30 Uhr, CAP 4 (Hochhaus)  Raum 1001

Weitere Informationen im Univis