National and Kapodistrian University of Athens
Approximation Algorithms for the Precedence Constrained Minimum Knapsack and Capacitated Covering Integer Programs
Abstract
dc:descriptionΣτην διπλωματική το κύριο πρόβλημα μελέτης είναι το πρόβλημα του knapsack και ειδικότερα μία γενίκευσή του στην οποία υπάρχει μία έννοια προτεραιότητας ως προς την επιλογή των αντικειμένων. Αρχικά παρουσιάζουμε το πρόβλημα του minimum knapsack με σκοπό να εισάγουμε κάποιες χρήσιμες τεχνικές με τις οποίες μπορούμε να κατασκευάσουμε primal-dual αλγορίθμους για το πρόβλημα. Ύστερα, εστιάζουμε την προσοχή μας στο γενικευμένο πρόβλημα precedence constrained minimum knapsack, το οποίο είναι παρόμοιο με το knapsack με τον επιπλέον περιορισμό ότι η επιλογή των αντικειμένων πρέπει να σέβεται μία έννοια προτεραιότητας που ορίζεται μέσω μίας μερικής διάταξης. Για το πρόβλημα αυτό, μελετάμε κάποια γραμμικά προγράμματα μαζί με τις ιδιότητές τους. Ακόμα, κατασκευάζουμε έναν προσεγγιστικό αλγόριθμο στρογγυλοποίησης για το 0-1 PCKP και παρουσιάζουμε κάποια νέα αποτελέσματα για το PCKP για την περίπτωση που μπορούμε να διαλέξουμε κάποιο αντικείμενο και πάνω από μία φορά. Στο τέλος του PCKP κεφαλαίου, ένα ήδη γνωστό αποτέλεσμα κάτω φράγματος παρουσιάζεται με λίγο διαφορετικό τρόπο. Τέλος, μελετάμε τα capacitated covering ακέραια προγράμματος και εμπνευσμένοι από γνωστές τεχνικές, δίνουμε κάποια αποτελέσματα για την ειδική περίπτωση 0-1 CIP.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Σκαρλάτος Αντώνιος
- Skarlatos Antonios
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, English, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:2940037