Μονάδα:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)Πληροφορική
Ημερομηνία κατάθεσης:
2021-03-23
Συγγραφέας:
Σκαρλάτος Αντώνιος
Στοιχεία επιβλεπόντων καθηγητών:
Κολλιόπουλος Σταύρος, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
Approximation Algorithms for the Precedence Constrained Minimum Knapsack and Capacitated Covering Integer Programs
Γλώσσες εργασίας:
Αγγλικά
Ελληνικά
Μεταφρασμένος τίτλος:
Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Knapsack με περιορισμό προτεραιότητας και για Ακέραια Προβλήματα Κάλυψης με χωρητικότητα
Περίληψη:
Στην διπλωματική το κύριο πρόβλημα μελέτης είναι το πρόβλημα του knapsack και ειδικότερα μία γενίκευσή του στην οποία υπάρχει μία έννοια προτεραιότητας ως
προς την επιλογή των αντικειμένων. Αρχικά παρουσιάζουμε το πρόβλημα του minimum knapsack με σκοπό να εισάγουμε κάποιες χρήσιμες τεχνικές με τις οποίες
μπορούμε να κατασκευάσουμε primal-dual αλγορίθμους για το πρόβλημα. Ύστερα, εστιάζουμε την προσοχή μας στο γενικευμένο πρόβλημα precedence constrained
minimum knapsack, το οποίο είναι παρόμοιο με το knapsack με τον επιπλέον περιορισμό ότι η επιλογή των αντικειμένων πρέπει να σέβεται μία έννοια
προτεραιότητας που ορίζεται μέσω μίας μερικής διάταξης. Για το πρόβλημα αυτό, μελετάμε κάποια γραμμικά προγράμματα μαζί με τις ιδιότητές τους.
Ακόμα, κατασκευάζουμε έναν προσεγγιστικό αλγόριθμο στρογγυλοποίησης για το 0-1 PCKP και παρουσιάζουμε κάποια νέα αποτελέσματα για το PCKP
για την περίπτωση που μπορούμε να διαλέξουμε κάποιο αντικείμενο και πάνω από μία φορά. Στο τέλος του PCKP κεφαλαίου, ένα ήδη γνωστό αποτέλεσμα
κάτω φράγματος παρουσιάζεται με λίγο διαφορετικό τρόπο. Τέλος, μελετάμε τα capacitated covering ακέραια προγράμματος και εμπνευσμένοι από γνωστές
τεχνικές, δίνουμε κάποια αποτελέσματα για την ειδική περίπτωση 0-1 CIP.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
προσεγγιστικοί αλγόριθμοι, γραμμικός προγραμματισμός, προβλημα σακιδιου, ακέραια προγράμματα
Αρ. σελίδων ευρετηρίου:
1
Αρ. βιβλιογραφικών αναφορών:
19
