Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2015-07-30
Στοιχεία επιβλεπόντων καθηγητών:
Βασίλειος Ζησιμόπουλος - Καθηγητής ΕΚΠΑ
Πρωτότυπος Τίτλος:
Approximation algorithms on network resource allocation
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Προσεγγιστικοί αλγόριθμοι ανάθεσης πόρων σε δίκτυα
Περίληψη:
Τα προβλήματα Ανάθεσης Πόρων (Resource Allocation Problems) θεωρούνται
ιδιαίτερης σημασίας όχι μόνο από τη θεωρητική σκοπιά, αλλά επίσης λόγω των
εφαρμογών τους στο σχεδιασμό δικτύων. Κεντρική θέση σε αυτήν την περιοχή
κατέχουν τα επονομαζόμενα προβλήματα Τοποθέτησης
Εργοστασίων (Facility Location Problems), όπου δεδομένων ενός συνόλου από
εργοστάσια/υποδομές με έξοδα εκκίνησης λειτουργίας και ενός συνόλου πελατών με
κάποια ζήτηση υπηρεσιών και τα αντίστοιχα έξοδα σύνδεσης, ο σκοπός είναι να
ικανοποιηθούν τα αιτήματα των πελατών ελαχιστοποιώντας ταυτόχρονα το συνολικό
κόστος. Αυτή η οικόγενεια προβλημάτων είναι ήδη καταγεγραμμένη από το '60,
ωστόσο δεν ήταν παρά μέχρι τα μέσα του 90' που άρχισε να σημειώνεται
αξιοσημείωτη πρόοδος από την προσεγγιστική πλευρά. Έκτοτε έχουν παρουσιασθεί
πολλές εκδοχές του προβλήματος και αποτελέσματα.
Σε αυτήν την εργασία εξετάζονται ορισμένες από τις πιο αντιπροσωπευτικές
παραλλαγές κάνοντας παράλληλα μια σύγκριση των τεχνικών που έχουν
χρησιμοποιηθεί ως τώρα, με πιο εξέχουσες τις τεχνικές που βασίζονται σε
γραμμικό προγραμματισμό και την τοπική αναζήτηση.
Αρχικά γίνεται μια πλήρης περιγραφή του βασικού προβλήματος χωρίς χωρητικότητες
(Uncapacitated
Facility Location Problem) και κατόπιν συνεχίζεται στο πιο γενικό πλαίσιο των
Fault-Tolerant αιτημάτων. Ακολούθως αναλύονται μια έκδοση με χωρητικότητα, μια
παραλλαγή με ακραίες τιμές και γενικεύσεις του αρχικού προβλήματος. Επίσης,
εξετάζεται η περίπτωση όπου εισάγεται η έννοια του χρόνου, οδηγώντας έτσι στην
κατηγορία των leasing προβλημάτων
Λέξεις-κλειδιά:
Προβλήματα Ανάθεσης Πόρων, Προβλήματα Τοποθέτησης Σταθμών Εξυπηρέτησης, Μίσθωση Σταθμών Εξυπηρέτηση, Ζητούμενα Ανεκτικότητας σε Σφάλματα, Συνδυαστική Βελτιστοποίηση
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
56
Αρχείο:
Δεν επιτρέπεται η πρόσβαση στο αρχείο.
document.pdf
613 KB
Δεν επιτρέπεται η πρόσβαση στο αρχείο.
