{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1319647"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1319647","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Προσεγγιστικοί αλγόριθμοι για το Generalized Min-Sum Set Cover","abstract":"Στην παρούσα εργασία, μελετάμε προσεγγιστικούς αλγόριθμους, βασισμένους στο γραμμικό προγραμματισμό, για το πρόβλημα Generalized Min-Sum Set Cover ή Multiple Intents Re-Ranking, Σε αυτό το NP-hard πρόβλημα, μας δίνεται μια συλλογή από σύνολα. Το κάθε σύνολο S έχει μια απαραίτητη προϋπόθεση κάλυψης K(S). Στόχος είναι να διατάξουμε τα στοιχεία των συνόλων σε τέτοια σειρά ώστε ο μέσος χρόνος κάλυψης των συνόλων να ελαχιστοποιηθεί. Χρόνος κάλυψης ενός συνόλου S είναι το ελάχιστο i για το οποίο K(S) στοιχεία του περιέχονται στις πρώτες i θέσεις της διάταξης. Μέσω της μελέτης των κυριότερων προσεγγιστικών αλγορίθμων για το πρόβλημα, αντιμετωπίζουμε την εξέλιξη και βελτίωση των τεχνικών που έχουν αναπτυχθεί και την επίπτωση αυτών στο ζητούμενο, την εγγύηση απόδοσης.","abstract_html":"Στην παρούσα εργασία, μελετάμε προσεγγιστικούς αλγόριθμους, βασισμένους στο γραμμικό προγραμματισμό, για το πρόβλημα Generalized Min-Sum Set Cover ή Multiple Intents Re-Ranking, Σε αυτό το NP-hard πρόβλημα, μας δίνεται μια συλλογή από σύνολα. Το κάθε σύνολο S έχει μια απαραίτητη προϋπόθεση κάλυψης K(S). Στόχος είναι να διατάξουμε τα στοιχεία των συνόλων σε τέτοια σειρά ώστε ο μέσος χρόνος κάλυψης των συνόλων να ελαχιστοποιηθεί. Χρόνος κάλυψης ενός συνόλου S είναι το ελάχιστο i για το οποίο K(S) στοιχεία του περιέχονται στις πρώτες i θέσεις της διάταξης. Μέσω της μελέτης των κυριότερων προσεγγιστικών αλγορίθμων για το πρόβλημα, αντιμετωπίζουμε την εξέλιξη και βελτίωση των τεχνικών που έχουν αναπτυχθεί και την επίπτωση αυτών στο ζητούμενο, την εγγύηση απόδοσης.","abstract_has_math":false,"creators":["Δημητρακόπουλος Θεόδωρος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-11-19T05:26:04Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1319647"],"render_values":[{"text":"uoadl:1319647","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1319647","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1319647","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1319647","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Δημητρακόπουλος Θεόδωρος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1319647","https://pergamos.lib.uoa.gr/uoa/dl/object/1319647"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Στην παρούσα εργασία, μελετάμε προσεγγιστικούς αλγόριθμους, βασισμένους στο γραμμικό προγραμματισμό, για το πρόβλημα Generalized Min-Sum Set Cover ή Multiple Intents Re-Ranking, Σε αυτό το NP-hard πρόβλημα, μας δίνεται μια συλλογή από σύνολα. Το κάθε σύνολο S έχει μια απαραίτητη προϋπόθεση κάλυψης K(S). Στόχος είναι να διατάξουμε τα στοιχεία των συνόλων σε τέτοια σειρά ώστε ο μέσος χρόνος κάλυψης των συνόλων να ελαχιστοποιηθεί. Χρόνος κάλυψης ενός συνόλου S είναι το ελάχιστο i για το οποίο K(S) στοιχεία του περιέχονται στις πρώτες i θέσεις της διάταξης. Μέσω της μελέτης των κυριότερων προσεγγιστικών αλγορίθμων για το πρόβλημα, αντιμετωπίζουμε την εξέλιξη και βελτίωση των τεχνικών που έχουν αναπτυχθεί και την επίπτωση αυτών στο ζητούμενο, την εγγύηση απόδοσης.","In this paper, we study approximation algorithms, based on linear programming, for the Generalized Min-Sum Set Cover or Multiple Intents Re-Ranking problem. In this NP-hard problem, we are given a collection of sets. Each set S has a necessary cover condition K (S). The goal is to order all the elements of the sets so as to minimize the total cover time. The cover time of a set S is the least index i in the ordering such that the first i elements in the ordering contain K(S) elements in S. Through the study of the premier approximation algorithms for the problem, we become acquainted with the evolution and improvement of the techniques that have been developed and the their impact on the main issue, the performance guarantee."]},{"key":"dc:title","label":"Title","values":["Προσεγγιστικοί αλγόριθμοι για το Generalized Min-Sum Set Cover"]}]}],"canonical_facts":{"dc:creator":["Δημητρακόπουλος Θεόδωρος"],"dc:date":["2014"],"dc:description":["Στην παρούσα εργασία, μελετάμε προσεγγιστικούς αλγόριθμους, βασισμένους στο γραμμικό προγραμματισμό, για το πρόβλημα Generalized Min-Sum Set Cover ή Multiple Intents Re-Ranking, Σε αυτό το NP-hard πρόβλημα, μας δίνεται μια συλλογή από σύνολα. Το κάθε σύνολο S έχει μια απαραίτητη προϋπόθεση κάλυψης K(S). Στόχος είναι να διατάξουμε τα στοιχεία των συνόλων σε τέτοια σειρά ώστε ο μέσος χρόνος κάλυψης των συνόλων να ελαχιστοποιηθεί. Χρόνος κάλυψης ενός συνόλου S είναι το ελάχιστο i για το οποίο K(S) στοιχεία του περιέχονται στις πρώτες i θέσεις της διάταξης. Μέσω της μελέτης των κυριότερων προσεγγιστικών αλγορίθμων για το πρόβλημα, αντιμετωπίζουμε την εξέλιξη και βελτίωση των τεχνικών που έχουν αναπτυχθεί και την επίπτωση αυτών στο ζητούμενο, την εγγύηση απόδοσης.","In this paper, we study approximation algorithms, based on linear programming, for the Generalized Min-Sum Set Cover or Multiple Intents Re-Ranking problem. In this NP-hard problem, we are given a collection of sets. Each set S has a necessary cover condition K (S). The goal is to order all the elements of the sets so as to minimize the total cover time. The cover time of a set S is the least index i in the ordering such that the first i elements in the ordering contain K(S) elements in S. Through the study of the premier approximation algorithms for the problem, we become acquainted with the evolution and improvement of the techniques that have been developed and the their impact on the main issue, the performance guarantee."],"dc:identifier":["uoadl:1319647","https://pergamos.lib.uoa.gr/uoa/dl/object/1319647"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Προσεγγιστικοί αλγόριθμοι για το Generalized Min-Sum Set Cover"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:04Z"}