National and Kapodistrian University of Athens
Προσεγγιστικοί αλγόριθμοι για το Generalized Min-Sum Set Cover
Abstract
dc:descriptionΣτην παρούσα εργασία, μελετάμε προσεγγιστικούς αλγόριθμους, βασισμένους στο γραμμικό προγραμματισμό, για το πρόβλημα Generalized Min-Sum Set Cover ή Multiple Intents Re-Ranking, Σε αυτό το NP-hard πρόβλημα, μας δίνεται μια συλλογή από σύνολα. Το κάθε σύνολο S έχει μια απαραίτητη προϋπόθεση κάλυψης K(S). Στόχος είναι να διατάξουμε τα στοιχεία των συνόλων σε τέτοια σειρά ώστε ο μέσος χρόνος κάλυψης των συνόλων να ελαχιστοποιηθεί. Χρόνος κάλυψης ενός συνόλου S είναι το ελάχιστο i για το οποίο K(S) στοιχεία του περιέχονται στις πρώτες i θέσεις της διάταξης. Μέσω της μελέτης των κυριότερων προσεγγιστικών αλγορίθμων για το πρόβλημα, αντιμετωπίζουμε την εξέλιξη και βελτίωση των τεχνικών που έχουν αναπτυχθεί και την επίπτωση αυτών στο ζητούμενο, την εγγύηση απόδοσης.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Δημητρακόπουλος Θεόδωρος
Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1319647