Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18179
Τίτλος: | Αλγόριθμοι για το πρόβλημα του Ελαχίστου Συνδετικού Δέντρου σε Χρονικά Μεταβαλλόμενα Στιγμιότυπα |
Συγγραφείς: | Βιδαλάκης, Γεώργιος Φωτάκης Δημήτριος |
Λέξεις κλειδιά: | Συνδετικά Δέντρα Spanning Trees Μητροειδή Matroids Προσεγγιστικοί Αλγόριθμοι Approximation Algorithms Χρονομεταβλητά Στιγμιότυπα Time-Evolving Instances Γραμμικός Προγραμματισμός Linear Programming Άπληστοι Αλγόριθμοι Greedy Algorithms Υλοποιήσεις Implementations |
Ημερομηνία έκδοσης: | 11-Νοε-2021 |
Περίληψη: | Τα τελευταία χρόνια υπάρχει σημαντικό ερευνητικό ενδιαφέρον για αλγοριθμους ελαχιστοποίησης κόστους σε κλασσικά προβλήματα βελτιστοποίησης με χρονικά μεταβαλλομένα στιγμιότυπα. Σε ένα πρόβλημα αυτού του είδους, πρέπει να υπολογίζονται οι χρονομεταβλητές παράμετροι ενός συστήματος για ένα πεπερασμένο σύνολο χρονικών στιγμών, ώστε σε κάθε χρονική στιγμή να ικανοποιείται ένας περιορισμός. Το κόστος προς ελαχιστοποίηση προκύπτει ως άθροισμα από ανεξάρτητα κόστη για τις επιμέρους χρονικές στιγμές και από κόστη μεταβολής του συστήματος, με το κόστος μεταβολής να αυξάνεται όσο πιο έντονες είναι οι αλλαγές του συστήματος μεταξύ διαδοχικών χρονικών στιγμών. Για τα προβλήματα αυτά, εκτός από την offline υπάρχει και η online εκδοχή όπου η ανεξάρτητη συνάρτηση κόστους κάθε χρονικής στιγμής δεν είναι γνωστή πριν από τη στιγμή αυτή. ΄Ενα από τα πρώτα προβλήματα αυτού του είδους που μελετήθηκε είναι το Multistage Matroid Maintenance, όπου κάθε χρονική στιγμή πρέπει να επιλέγεται ένα σύνολο στοιχείων, ώστε να διατηρείται μία βάση του μητροειδούς, και με το κόστος να προκύπτει από τα στιγμιαία κόστη των στοιχείων και από το πλήθος των αλλαγών επιλογής ανά στοιχείο. Οι (Gupta, Talwar, Wieder, ICALP 2014) έδωσαν διαφόρους λογαριθμικούς προσεγγιστικούς αλγορίθμους για το πρόβλημα αυτό, ενώ εξέτασαν ειδικές περιπτώσεις μητροειδών και την online εκδοχή του προβλήματος. Στη διπλωματική αυτή εργασία μελετάται το Multistage Matroid Maintenance στην ειδική περίπτωση που το μητροειδές είναι γραφικό και το κόστος επιλογής νέου στοιχείου (ακμής) είναι κοινό για κάθε στοιχείο και χρονική στιγμή, με στόχο τη βελτίωση των λόγων προσέγγισης. Δείχνεται ότι το άμεσο ανάλογο της dual fitting απόδειξης των (Gupta, Talwar, Wieder, ICALP 2014) δεν μπορεί να χρησιμοποιηθεί για την απόδειξη καλύτερου λόγου προσέγγισης από τον υπάρχοντα λογαριθμικό. Παρουσιάζεται ένας άπληστος αλγόριθμος και αποδεικνύεται ότι υπολογίζει βέλτιστη λύση σε διάφορες οικογένειες στιγμιοτύπων, συγκεκριμένα σε στιγμιότυπα με γράφημα όπου κάθε ακμή ανήκει σε έναν το πολύ κύκλο και σε στιγμιότυπα με μέχρι και τρεις χρονικές στιγμές. Ακόμη, αποδεικνύεται ένα σύνολο συνδυαστικών ιδιοτήτων οι οποίες έχουν ανεξάρτητο ενδιαφέρον και ενδέχεται να είναι χρήσιμες για την περαιτέρω ενασχόληση με το πρόβλημα αυτό. Τέλος, παρουσιάζεται ένα σύνολο παραμετρικών αλγορίθμων για τον υπολογισμό της βέλτιστης λύσης καθώς και των ορίων κόστους των λύσεων του απλήστου αλγορίθμου για δεδομένα στιγμιότυπα, οι οποίοι μάλιστα έχουν υλοποιηθεί και αξιολογηθεί πειραματικά. |
URI: | http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18179 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Περιγραφή | Μέγεθος | Μορφότυπος | |
---|---|---|---|---|
thesis_el15052.pdf | 906.89 kB | Adobe PDF | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.