Μέση Και Χειρότερη Επίδοση Online Και Offline Αλγόριθμων Για Το Bin Packing.

Abstract

Ο σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη του NP-Hard προβλήματος του $Bin$ $Packing$. Η εργασία ξεκινάει με μία εισαγωγή στη θεωρία της πολυπλοκότητας και τον ορισμό κάποιων πολύ βασικών εννοιών. Στη συνέχεια γίνεται μία εισαγωγή στο πρόβλημα και η αναφορά των κυριότερων κατηγοριών αλγορίθμων που το επιλύουν. Γίνεται αναλυτική μελέτη ενός πλήθους προσσεγγίστικων αλγορίθμων που επιλύουν το Bin Packing. Η μελέτη αυτή περιλαμβάνει ανάλυση των χειρότερων (worst-case) αλλά και των μέσων επιδόσεων (average-case) τους. Αναφέρονται πολλά θεωρήματα με τις αποδείξεις τους. Γίνεται επίσης εφαρμογή αρκετών αλγορίθμων για συγκεκριμένη είσοδο και σύγκριση των αποδόσεων τους. Υπάρχει αναλυτική αναφορά σε ένα PTAS μεαποδείξεις όλων των θεωρημάτων που το συνοδεύουν. Τέλοςαναφέρονται δύο πολύ πρόσφατοι αλγόριθμοι και μελετώνται οιεπιδόσεις τους.