1. Home page
  2. Search

Αλγόριθμοι καθοδηγούμενοι από δεδομένα για προβλήματα συνεκτικότητας σε γραφήματα

This item is provided by the institution :
National Technical University of Athens   

Repository :
Digital Library of National Technical University of Athens | Dspace@NTUA   

see the original item page
in the repository's web site and access all digital files if the item*



Αλγόριθμοι καθοδηγούμενοι από δεδομένα για προβλήματα συνεκτικότητας σε γραφήματα (EL)
Στούρας, Μιλτιάδης (EL)
Stouras, Miltiadis (EN)
ntua (EL)
Φωτάκης, Δημήτριος (EL)
Στούρας, Μιλτιάδης (EL)
Τζάμος, Χρήστος (EL)
Παγουρτζής, Αριστείδης (EL)
Fotakis, Dimitris (EN)
bachelorThesis
2022-07-28T11:40:59Z
2022-03-04
Η παρούσα διπλωματική εργασία μελετά το πρόβλημα της συνεκτικότητας γραφημάτων υπό την σκοπιά του τομέα Data-Driven Algorithm Design. Η συνεκτικότητα γραφημάτων είναι ένα θεμελιώδες πρόβλημα συνδιαστικής βελτιστοποίησης που συναντάται αρκετά συχνά σε πρακτικά προβλήματα και πολλές φορές σε στοχαστικό περιβάλλον. Ένα τέτοιο παράδειγμα αποτελούν τα δίκτυα υπολογιστών τα οποία βασίζονται στην συνεκτικότητά τους για να λειτουργούν. Πολλές φορές, όμως, οι συνδέσεις μεταξύ υπολογιστών μπορεί να είναι αναξιόποιηστες (π.χ. να έχουν υψηλό θόρυβο) ή να έχουν βγει προσωρινά εκτός λειτουργίας. Μετά από κάποιο φυσικό συμβάν που μπορεί να θέσει εκτός λειτουργίας διάφορες συνδέσεις του δικτύου, θα θέλαμε να μπορούμε να βρούμε ένα συνδετικό δέντρο ώστε να επαναφέρουμε το δίκτυο σε λειτουργία. Ωστόσο, ο έλεγχος για την λειτουργικότητα συνδέσεων μπορεί να είναι αρκετά κοστοβόρος, επομένως το ζητούμενο είναι να ανακαλύψουμε ένα συνδετικό δέντρο κάνοντας όσο λιγότερους ελέγχους μπορούμε. Ακολουθώντας την γραμμή έρευνας που ξεκίνησε από τους Chawla et al. (FOCS 2020), ορίζουμε δύο κλάσεις αλγορίθμων με βάση την προσαρμοστικότητά τους και προσπαθούμε να προσεγγίσουμε το κόστος της βέλτιστης μη-προσαρμοστικής στρατηγικής για την κατανομή εισόδων που αντιμετωπίζουμε. Αποδεικνύουμε ότι είναι NP-hard να προσεγγίσουμε το κόστος της βέλτιστης μη-προσαρμοστικής στρατηγικής με λόγο προσέγγισης μικρότερο από λογαριθμικό χρησιμοποιώντας έναν υπολογιστικά αποδοτικό μη-προσαρμοστικό αλγόριθμο και σχεδιάζουμε προσαρμοστικούς αλγορίθμους που καταφέρνουν να προσεγγίσουν το κόστος αυτό με σταθερό λόγο προσέγγισης σε διάφορες οικογένειες γραφημάτων. (EL)
Αλγόριθμοι καθοδηγούμενοι από δεδομένα (EL)
Τυχαία γραφήματα (EL)
Graph connectivity (EL)
Random graphs (EL)
Adaptive algorithms (EL)
Συνεκτικότητα γραφημάτων (EL)
Αξιοποίηση δεδομένων (EL)
Προσαρμοστικοί αλγόριθμοι (EL)
Treewidth (EL)
Data-driven algorithms (EN)
Greek
English
Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (EL)
Αναφορά Δημιουργού 3.0 Ελλάδα
http://creativecommons.org/licenses/by/3.0/gr/
National Technical University of Athens
Digital Library of National Technical University of Athens | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Διπλωματικές Εργασίες



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)