Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Δημητρακόπουλος Θεόδωρος. Προσεγγιστικοί αλγόριθμοι για το Generalized Min-Sum Set Cover. 2014. https://pergamos.lib.uoa.gr/uoa/dl/object/1319647