1. Αρχική σελίδα
  2. Αναζήτηση

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

Το τεκμήριο παρέχεται από τον φορέα :
Εθνικό Μετσόβιο Πολυτεχνείο   

Αποθετήριο :
Ψηφιακό Αποθετήριο της Κεντρικής Βιβλιοθήκης του ΕΜΠ | Dspace@NTUA   

δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*



Αλγόριθμοι καθοδηγούμενοι από δεδομένα για προβλήματα συνεκτικότητας σε γραφήματα (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)
Ελληνική γλώσσα
Αγγλική γλώσσα
Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (EL)
Αναφορά Δημιουργού 3.0 Ελλάδα
http://creativecommons.org/licenses/by/3.0/gr/
Εθνικό Μετσόβιο Πολυτεχνείο
Ψηφιακό Αποθετήριο της Κεντρικής Βιβλιοθήκης του ΕΜΠ | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Διπλωματικές Εργασίες



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.