Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14036
Title: | Μέση Και Χειρότερη Επίδοση Online Και Offline Αλγόριθμων Για Το Bin Packing. |
Authors: | Μαυρακάκης Ιωάννης Αφράτη Φώτω |
Keywords: | bin packing πολυπλοκότητα προσσεγγιστικοί αλγόριθμοι average-case ανάλυση worst-case ανάλυση offline αλγόριθμοι online αλγόριθμοι bounded-space αλγόριθμοι pταs αλυσίδες markov. |
Issue Date: | 12-Jul-2004 |
Abstract: | Ο σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη του NP-Hard προβλήματος του $Bin$ $Packing$. Η εργασία ξεκινάει με μία εισαγωγή στη θεωρία της πολυπλοκότητας και τον ορισμό κάποιων πολύ βασικών εννοιών. Στη συνέχεια γίνεται μία εισαγωγή στο πρόβλημα και η αναφορά των κυριότερων κατηγοριών αλγορίθμων που το επιλύουν. Γίνεται αναλυτική μελέτη ενός πλήθους προσσεγγίστικων αλγορίθμων που επιλύουν το Bin Packing. Η μελέτη αυτή περιλαμβάνει ανάλυση των χειρότερων (worst-case) αλλά και των μέσων επιδόσεων (average-case) τους. Αναφέρονται πολλά θεωρήματα με τις αποδείξεις τους. Γίνεται επίσης εφαρμογή αρκετών αλγορίθμων για συγκεκριμένη είσοδο και σύγκριση των αποδόσεων τους. Υπάρχει αναλυτική αναφορά σε ένα PTAS μεαποδείξεις όλων των θεωρημάτων που το συνοδεύουν. Τέλοςαναφέρονται δύο πολύ πρόσφατοι αλγόριθμοι και μελετώνται οιεπιδόσεις τους. |
URI: | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14036 |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2004-0075.ps | 893.23 kB | Postscript | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.