Masterprojekt Algorithm Engineering
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
Organisatorisches
Vorbesprechung: Freitag 30. 10. 2015, 11:30 Uhr, CAP 4 (Hochhaus) Raum 1001
Weitere Informationen im Univis