{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1320899"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1320899","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Approximation algorithms on network resource allocation","abstract":"Τα προβλήματα Ανάθεσης Πόρων (Resource Allocation Problems) θεωρούνται ιδιαίτερης σημασίας όχι μόνο από τη θεωρητική σκοπιά, αλλά επίσης λόγω των εφαρμογών τους στο σχεδιασμό δικτύων. Κεντρική θέση σε αυτήν την περιοχή κατέχουν τα επονομαζόμενα προβλήματα Τοποθέτησης Εργοστασίων (Facility Location Problems), όπου δεδομένων ενός συνόλου από εργοστάσια/υποδομές με έξοδα εκκίνησης λειτουργίας και ενός συνόλου πελατών με κάποια ζήτηση υπηρεσιών και τα αντίστοιχα έξοδα σύνδεσης, ο σκοπός είναι να ικανοποιηθούν τα αιτήματα των πελατών ελαχιστοποιώντας ταυτόχρονα το συνολικό κόστος. Αυτή η οικόγενεια προβλημάτων είναι ήδη καταγεγραμμένη από το '60, ωστόσο δεν ήταν παρά μέχρι τα μέσα του 90' που άρχισε να σημειώνεται αξιοσημείωτη πρόοδος από την προσεγγιστική πλευρά. Έκτοτε έχουν παρουσιασθεί πολλές εκδοχές του προβλήματος και αποτελέσματα. Σε αυτήν την εργασία εξετάζονται ορισμένες από τις πιο αντιπροσωπευτικές παραλλαγές κάνοντας παράλληλα μια σύγκριση των τεχνικών που έχουν χρησιμοποιηθεί ως τώρα, με πιο εξέχουσες τις τεχνικές που βασίζονται σε γραμμικό προγραμματισμό και την τοπική αναζήτηση. Αρχικά γίνεται μια πλήρης περιγραφή του βασικού προβλήματος χωρίς χωρητικότητες (Uncapacitated Facility Location Problem) και κατόπιν συνεχίζεται στο πιο γενικό πλαίσιο των Fault-Tolerant αιτημάτων. Ακολούθως αναλύονται μια έκδοση με χωρητικότητα, μια παραλλαγή με ακραίες τιμές και γενικεύσεις του αρχικού προβλήματος. Επίσης, εξετάζεται η περίπτωση όπου εισάγεται η έννοια του χρόνου, οδηγώντας έτσι στην κατηγορία των leasing προβλημάτων","abstract_html":"Τα προβλήματα Ανάθεσης Πόρων (Resource Allocation Problems) θεωρούνται ιδιαίτερης σημασίας όχι μόνο από τη θεωρητική σκοπιά, αλλά επίσης λόγω των εφαρμογών τους στο σχεδιασμό δικτύων. Κεντρική θέση σε αυτήν την περιοχή κατέχουν τα επονομαζόμενα προβλήματα Τοποθέτησης Εργοστασίων (Facility Location Problems), όπου δεδομένων ενός συνόλου από εργοστάσια/υποδομές με έξοδα εκκίνησης λειτουργίας και ενός συνόλου πελατών με κάποια ζήτηση υπηρεσιών και τα αντίστοιχα έξοδα σύνδεσης, ο σκοπός είναι να ικανοποιηθούν τα αιτήματα των πελατών ελαχιστοποιώντας ταυτόχρονα το συνολικό κόστος. Αυτή η οικόγενεια προβλημάτων είναι ήδη καταγεγραμμένη από το &#x27;60, ωστόσο δεν ήταν παρά μέχρι τα μέσα του 90&#x27; που άρχισε να σημειώνεται αξιοσημείωτη πρόοδος από την προσεγγιστική πλευρά. Έκτοτε έχουν παρουσιασθεί πολλές εκδοχές του προβλήματος και αποτελέσματα. Σε αυτήν την εργασία εξετάζονται ορισμένες από τις πιο αντιπροσωπευτικές παραλλαγές κάνοντας παράλληλα μια σύγκριση των τεχνικών που έχουν χρησιμοποιηθεί ως τώρα, με πιο εξέχουσες τις τεχνικές που βασίζονται σε γραμμικό προγραμματισμό και την τοπική αναζήτηση. Αρχικά γίνεται μια πλήρης περιγραφή του βασικού προβλήματος χωρίς χωρητικότητες (Uncapacitated Facility Location Problem) και κατόπιν συνεχίζεται στο πιο γενικό πλαίσιο των Fault-Tolerant αιτημάτων. Ακολούθως αναλύονται μια έκδοση με χωρητικότητα, μια παραλλαγή με ακραίες τιμές και γενικεύσεις του αρχικού προβλήματος. Επίσης, εξετάζεται η περίπτωση όπου εισάγεται η έννοια του χρόνου, οδηγώντας έτσι στην κατηγορία των leasing προβλημάτων","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":2015,"date_issued":"2015","date_published":"2015","updated_at":"2026-11-19T05:26:32Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320899"],"render_values":[{"text":"uoadl:1320899","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320899","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320899","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%3A1320899","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":["2015"]},{"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":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320899","https://pergamos.lib.uoa.gr/uoa/dl/object/1320899"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Τα προβλήματα Ανάθεσης Πόρων (Resource Allocation Problems) θεωρούνται ιδιαίτερης σημασίας όχι μόνο από τη θεωρητική σκοπιά, αλλά επίσης λόγω των εφαρμογών τους στο σχεδιασμό δικτύων. Κεντρική θέση σε αυτήν την περιοχή κατέχουν τα επονομαζόμενα προβλήματα Τοποθέτησης Εργοστασίων (Facility Location Problems), όπου δεδομένων ενός συνόλου από εργοστάσια/υποδομές με έξοδα εκκίνησης λειτουργίας και ενός συνόλου πελατών με κάποια ζήτηση υπηρεσιών και τα αντίστοιχα έξοδα σύνδεσης, ο σκοπός είναι να ικανοποιηθούν τα αιτήματα των πελατών ελαχιστοποιώντας ταυτόχρονα το συνολικό κόστος. Αυτή η οικόγενεια προβλημάτων είναι ήδη καταγεγραμμένη από το '60, ωστόσο δεν ήταν παρά μέχρι τα μέσα του 90' που άρχισε να σημειώνεται αξιοσημείωτη πρόοδος από την προσεγγιστική πλευρά. Έκτοτε έχουν παρουσιασθεί πολλές εκδοχές του προβλήματος και αποτελέσματα. Σε αυτήν την εργασία εξετάζονται ορισμένες από τις πιο αντιπροσωπευτικές παραλλαγές κάνοντας παράλληλα μια σύγκριση των τεχνικών που έχουν χρησιμοποιηθεί ως τώρα, με πιο εξέχουσες τις τεχνικές που βασίζονται σε γραμμικό προγραμματισμό και την τοπική αναζήτηση. Αρχικά γίνεται μια πλήρης περιγραφή του βασικού προβλήματος χωρίς χωρητικότητες (Uncapacitated Facility Location Problem) και κατόπιν συνεχίζεται στο πιο γενικό πλαίσιο των Fault-Tolerant αιτημάτων. Ακολούθως αναλύονται μια έκδοση με χωρητικότητα, μια παραλλαγή με ακραίες τιμές και γενικεύσεις του αρχικού προβλήματος. Επίσης, εξετάζεται η περίπτωση όπου εισάγεται η έννοια του χρόνου, οδηγώντας έτσι στην κατηγορία των leasing προβλημάτων","Resource Allocation Problems are of particular importance not only from a theoretical aspect, but also due to their applications in network design. A central place in this area have occupied the so called Facility Location Problems, where given a set of facilities with opening costs and a set of clients with service demands and their respective connection costs, the objective is to satisfy the clients' demands while minimizing the total cost. This line of problems dates back to the 60's, however it was not until the mid-90's that a breakthrough was made in terms of approximation. Since then, numerous variants and results have appeared. In this work, some of the most representative variants are examined followed by a compar- ison of the techniques employed so far to tackle them, most prominently LP-based techniques and local search. We begin by a thorough presentation of the basic Uncapacitated Facility Lo- cation Problem and then continue with the more generic Fault-Tolerant setting. We proceed by analyzing a capacitated version, a variant with outliers and generalizations of the original problem. Finally, we examine the case where the notion of time is introduced, leading to Facility Leasing Problems."]},{"key":"dc:title","label":"Title","values":["Approximation algorithms on network resource allocation"]}]}],"canonical_facts":{"dc:creator":["Κουτλή Άννα"],"dc:date":["2015"],"dc:description":["Τα προβλήματα Ανάθεσης Πόρων (Resource Allocation Problems) θεωρούνται ιδιαίτερης σημασίας όχι μόνο από τη θεωρητική σκοπιά, αλλά επίσης λόγω των εφαρμογών τους στο σχεδιασμό δικτύων. Κεντρική θέση σε αυτήν την περιοχή κατέχουν τα επονομαζόμενα προβλήματα Τοποθέτησης Εργοστασίων (Facility Location Problems), όπου δεδομένων ενός συνόλου από εργοστάσια/υποδομές με έξοδα εκκίνησης λειτουργίας και ενός συνόλου πελατών με κάποια ζήτηση υπηρεσιών και τα αντίστοιχα έξοδα σύνδεσης, ο σκοπός είναι να ικανοποιηθούν τα αιτήματα των πελατών ελαχιστοποιώντας ταυτόχρονα το συνολικό κόστος. Αυτή η οικόγενεια προβλημάτων είναι ήδη καταγεγραμμένη από το '60, ωστόσο δεν ήταν παρά μέχρι τα μέσα του 90' που άρχισε να σημειώνεται αξιοσημείωτη πρόοδος από την προσεγγιστική πλευρά. Έκτοτε έχουν παρουσιασθεί πολλές εκδοχές του προβλήματος και αποτελέσματα. Σε αυτήν την εργασία εξετάζονται ορισμένες από τις πιο αντιπροσωπευτικές παραλλαγές κάνοντας παράλληλα μια σύγκριση των τεχνικών που έχουν χρησιμοποιηθεί ως τώρα, με πιο εξέχουσες τις τεχνικές που βασίζονται σε γραμμικό προγραμματισμό και την τοπική αναζήτηση. Αρχικά γίνεται μια πλήρης περιγραφή του βασικού προβλήματος χωρίς χωρητικότητες (Uncapacitated Facility Location Problem) και κατόπιν συνεχίζεται στο πιο γενικό πλαίσιο των Fault-Tolerant αιτημάτων. Ακολούθως αναλύονται μια έκδοση με χωρητικότητα, μια παραλλαγή με ακραίες τιμές και γενικεύσεις του αρχικού προβλήματος. Επίσης, εξετάζεται η περίπτωση όπου εισάγεται η έννοια του χρόνου, οδηγώντας έτσι στην κατηγορία των leasing προβλημάτων","Resource Allocation Problems are of particular importance not only from a theoretical aspect, but also due to their applications in network design. A central place in this area have occupied the so called Facility Location Problems, where given a set of facilities with opening costs and a set of clients with service demands and their respective connection costs, the objective is to satisfy the clients' demands while minimizing the total cost. This line of problems dates back to the 60's, however it was not until the mid-90's that a breakthrough was made in terms of approximation. Since then, numerous variants and results have appeared. In this work, some of the most representative variants are examined followed by a compar- ison of the techniques employed so far to tackle them, most prominently LP-based techniques and local search. We begin by a thorough presentation of the basic Uncapacitated Facility Lo- cation Problem and then continue with the more generic Fault-Tolerant setting. We proceed by analyzing a capacitated version, a variant with outliers and generalizations of the original problem. Finally, we examine the case where the notion of time is introduced, leading to Facility Leasing Problems."],"dc:identifier":["uoadl:1320899","https://pergamos.lib.uoa.gr/uoa/dl/object/1320899"],"dc:language":["English"],"dc:title":["Approximation algorithms on network resource allocation"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:32Z"}