Μονάδα:
Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2014-01-31
Συγγραφέας:
Δημητρακόπουλος Θεόδωρος
Στοιχεία επιβλεπόντων καθηγητών:
Σταύρος Κολλιόπουλος Αναπλ. Καθηγητής ΕΚΠΑ
Πρωτότυπος Τίτλος:
Προσεγγιστικοί αλγόριθμοι για το Generalized Min-Sum Set Cover
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
Approximation algorithms for the Generalized Min-Sum Set Cover
Περίληψη:
Στην παρούσα εργασία, μελετάμε προσεγγιστικούς αλγόριθμους, βασισμένους στο
γραμμικό προγραμματισμό, για το πρόβλημα Generalized Min-Sum Set Cover ή
Multiple Intents Re-Ranking, Σε αυτό το NP-hard πρόβλημα, μας δίνεται μια
συλλογή από σύνολα. Το κάθε σύνολο S έχει μια απαραίτητη προϋπόθεση κάλυψης
K(S). Στόχος είναι να διατάξουμε τα στοιχεία των συνόλων σε τέτοια σειρά ώστε ο
μέσος χρόνος κάλυψης των συνόλων να ελαχιστοποιηθεί. Χρόνος κάλυψης ενός
συνόλου S είναι το ελάχιστο i για το οποίο K(S) στοιχεία του περιέχονται στις
πρώτες i θέσεις της διάταξης. Μέσω της μελέτης των κυριότερων προσεγγιστικών
αλγορίθμων για το πρόβλημα, αντιμετωπίζουμε την εξέλιξη και βελτίωση των
τεχνικών που έχουν αναπτυχθεί και την επίπτωση αυτών στο ζητούμενο, την εγγύηση
απόδοσης.
Λέξεις-κλειδιά:
Γραμμικός προγράμματος, generalized min-sum set cover, Εγγύηση απόδοσης, α-points, Μητροειδές
Αρ. σελίδων ευρετηρίου:
9
Αρ. βιβλιογραφικών αναφορών:
42
