Ο φοιτητής του προγράμματος Αντώνιος Σκαρλάτος θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Approximation Algorithms for Precedence-Constrained Knapsack and Capacitated Covering Integer Programs
την Παρασκευή 12 Μαρτίου 2021 και ώρα 14:45, μέσω τηλεμετάδοσης *.
Σύνοψη Διπλωματικής:
Precedence-constrained knapsack is a generalization of the classical Minimum Knapsack problem in which the items chosen for inclusion in the knapsack must form a prefix (ideal) of a given partial order. We study primal-dual algorithms from the literature and among other results we settle the question of the existence of an approximation algorithm with strongly polynomial bounds for the case where item i can be chosen at most d_i times (as opposed to at most once).
Capacitated covering integer programs generalize Minimum Knapsack in the sense that the items chosen must satisfy simultaneously m covering constraints. For this problem we improve the efficiency of a known approximatio algorithms.
All our positive and negative results rely on linear programming relaxations for the problems.
Η Επιτροπή,
Αρχοντία Γιαννοπούλου,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Σταύρος Κολλιόπουλος (Επιβλέπων),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Δημήτρης Φωτάκης,
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
* Zoom link: https://us02web.zoom.us/j/88472152521?pwd=aHVrZTZpS2lxdDBWNHBoN0RHZ1Vqdz09