{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1722725"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1722725","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Δάσους Steiner","abstract":"Το πρόβλημα Δάσους Steiner είναι μία γενίκευση του προβλήματος Δέντρου Steiner και κατ’ επέκταση του Ελάχιστου Επικαλύπτοντος Δέντρου. Αυτά τα προβλήματα είναι ευρέως γνωστά προβλήματα συνδυαστικής βελτιστοποίησης. Επίσης, βρίσκουν πολλές εφαρμογές όπως, η σχεδίαση VLSI κυκλωμάτων, η σχεδίαση τηλεφωνικών δικτύων και η ανακατασκευή φυλογενετικών δέντρων. Επομένως, η μελέτη αυτών των προβλημάτων και η σχεδίαση αλγορίθμων, που τα επιλύουν, είναι σημαντική. Επιλύοντας τα γενικά προβλήματα επιλύουμε και όλα τα σχετικά πρακτικά προβλήματα. Έχει αποδειχθεί από τον Karp ότι το αντίστοιχο πρόβλημα απόφασης του Δέντρου Steiner, και κατ’ επέκταση του Δάσους Steiner, είναι NP-Πλήρες. Επομένως, το να βρούμε σε πωλυωνυμικό χρόνο τη βέλτιστη λύση είναι NP-Δύσκολο, το οποίο σημαίνει ότι θα πρέπει να σχεδιάσουμε προσεγγιστικούς αλγόριθμους. Για αρκετό χρονικό διάστημα οι καλύτεροι αλγόριθμοι συνδυαστικής φύσεως δεν είχαν κάποια σταθερή προσέγγιση, η μόνη 2-προσεγγιστική μέθοδος που είχαμε ήταν μια μέθοδος αρχικού - δυϊκού από την περιοχή του Γραμμικού Προγραμματισμού. Πρόσφατα, όμως, οι Gupta και Kumar μας έδωσαν έναν 96-προσεγγιστικό αλγόριθμο συνδυαστικής φύσεως. Καλούμαστε, λοιπόν, να βελτιώσουμε την ανάλυση αυτού του αλγόριθμου καθώς και να τον συγκρίνουμε με τον Άπληστο Αλγόριθμο, ο οποίος δεν έχει σταθερή προσέγγιση. Στην παρούσα διπλωματική εργασία δείξαμε ότι ο ”Αδηφάγος” Αλγόριθμος είναι 2-προσεγγιστικός στην κατηγορία των Δέντρων. Επίσης, πραγματοποιήθηκε μία υλοποίηση των δύο αλγορίθμων με σκοπό την πειραματική τους σύγκριση. Είδαμε ότι, οι δύο αλγόριθμοι βρίσκουν λύσεις πολύ κοντά στη βέλτιστη όσον αφορά τα Δέντρα, στην κατηγορία των Πλήρη γραφημάτων είδαμε ότι ο Άπληστος Αλγόριθμος έχει καλύτερη επίδοση και στην κατηγορία των Ψευδοτυχαίων γραφημάτων η επίδοση των αλγορίθμων είναι παρόμοια.","abstract_html":"Το πρόβλημα Δάσους Steiner είναι μία γενίκευση του προβλήματος Δέντρου Steiner και κατ’ επέκταση του Ελάχιστου Επικαλύπτοντος Δέντρου. Αυτά τα προβλήματα είναι ευρέως γνωστά προβλήματα συνδυαστικής βελτιστοποίησης. Επίσης, βρίσκουν πολλές εφαρμογές όπως, η σχεδίαση VLSI κυκλωμάτων, η σχεδίαση τηλεφωνικών δικτύων και η ανακατασκευή φυλογενετικών δέντρων. Επομένως, η μελέτη αυτών των προβλημάτων και η σχεδίαση αλγορίθμων, που τα επιλύουν, είναι σημαντική. Επιλύοντας τα γενικά προβλήματα επιλύουμε και όλα τα σχετικά πρακτικά προβλήματα. Έχει αποδειχθεί από τον Karp ότι το αντίστοιχο πρόβλημα απόφασης του Δέντρου Steiner, και κατ’ επέκταση του Δάσους Steiner, είναι NP-Πλήρες. Επομένως, το να βρούμε σε πωλυωνυμικό χρόνο τη βέλτιστη λύση είναι NP-Δύσκολο, το οποίο σημαίνει ότι θα πρέπει να σχεδιάσουμε προσεγγιστικούς αλγόριθμους. Για αρκετό χρονικό διάστημα οι καλύτεροι αλγόριθμοι συνδυαστικής φύσεως δεν είχαν κάποια σταθερή προσέγγιση, η μόνη 2-προσεγγιστική μέθοδος που είχαμε ήταν μια μέθοδος αρχικού - δυϊκού από την περιοχή του Γραμμικού Προγραμματισμού. Πρόσφατα, όμως, οι Gupta και Kumar μας έδωσαν έναν 96-προσεγγιστικό αλγόριθμο συνδυαστικής φύσεως. Καλούμαστε, λοιπόν, να βελτιώσουμε την ανάλυση αυτού του αλγόριθμου καθώς και να τον συγκρίνουμε με τον Άπληστο Αλγόριθμο, ο οποίος δεν έχει σταθερή προσέγγιση. Στην παρούσα διπλωματική εργασία δείξαμε ότι ο ”Αδηφάγος” Αλγόριθμος είναι 2-προσεγγιστικός στην κατηγορία των Δέντρων. Επίσης, πραγματοποιήθηκε μία υλοποίηση των δύο αλγορίθμων με σκοπό την πειραματική τους σύγκριση. Είδαμε ότι, οι δύο αλγόριθμοι βρίσκουν λύσεις πολύ κοντά στη βέλτιστη όσον αφορά τα Δέντρα, στην κατηγορία των Πλήρη γραφημάτων είδαμε ότι ο Άπληστος Αλγόριθμος έχει καλύτερη επίδοση και στην κατηγορία των Ψευδοτυχαίων γραφημάτων η επίδοση των αλγορίθμων είναι παρόμοια.","abstract_has_math":false,"creators":["Γιαχούδης Νικόλαος","Giachoudis Nikolaos"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017","date_published":"2017","updated_at":"2026-11-19T05:29:27Z","subjects":["Πληροφορική","Computer science"],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1722725"],"render_values":[{"text":"uoadl:1722725","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1722725","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1722725","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%3A1722725","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Γιαχούδης Νικόλαος","Giachoudis Nikolaos"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Πληροφορική","Computer science"]}]},{"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:1722725","https://pergamos.lib.uoa.gr/uoa/dl/object/1722725"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Το πρόβλημα Δάσους Steiner είναι μία γενίκευση του προβλήματος Δέντρου Steiner και κατ’ επέκταση του Ελάχιστου Επικαλύπτοντος Δέντρου. Αυτά τα προβλήματα είναι ευρέως γνωστά προβλήματα συνδυαστικής βελτιστοποίησης. Επίσης, βρίσκουν πολλές εφαρμογές όπως, η σχεδίαση VLSI κυκλωμάτων, η σχεδίαση τηλεφωνικών δικτύων και η ανακατασκευή φυλογενετικών δέντρων. Επομένως, η μελέτη αυτών των προβλημάτων και η σχεδίαση αλγορίθμων, που τα επιλύουν, είναι σημαντική. Επιλύοντας τα γενικά προβλήματα επιλύουμε και όλα τα σχετικά πρακτικά προβλήματα. Έχει αποδειχθεί από τον Karp ότι το αντίστοιχο πρόβλημα απόφασης του Δέντρου Steiner, και κατ’ επέκταση του Δάσους Steiner, είναι NP-Πλήρες. Επομένως, το να βρούμε σε πωλυωνυμικό χρόνο τη βέλτιστη λύση είναι NP-Δύσκολο, το οποίο σημαίνει ότι θα πρέπει να σχεδιάσουμε προσεγγιστικούς αλγόριθμους. Για αρκετό χρονικό διάστημα οι καλύτεροι αλγόριθμοι συνδυαστικής φύσεως δεν είχαν κάποια σταθερή προσέγγιση, η μόνη 2-προσεγγιστική μέθοδος που είχαμε ήταν μια μέθοδος αρχικού - δυϊκού από την περιοχή του Γραμμικού Προγραμματισμού. Πρόσφατα, όμως, οι Gupta και Kumar μας έδωσαν έναν 96-προσεγγιστικό αλγόριθμο συνδυαστικής φύσεως. Καλούμαστε, λοιπόν, να βελτιώσουμε την ανάλυση αυτού του αλγόριθμου καθώς και να τον συγκρίνουμε με τον Άπληστο Αλγόριθμο, ο οποίος δεν έχει σταθερή προσέγγιση. Στην παρούσα διπλωματική εργασία δείξαμε ότι ο ”Αδηφάγος” Αλγόριθμος είναι 2-προσεγγιστικός στην κατηγορία των Δέντρων. Επίσης, πραγματοποιήθηκε μία υλοποίηση των δύο αλγορίθμων με σκοπό την πειραματική τους σύγκριση. Είδαμε ότι, οι δύο αλγόριθμοι βρίσκουν λύσεις πολύ κοντά στη βέλτιστη όσον αφορά τα Δέντρα, στην κατηγορία των Πλήρη γραφημάτων είδαμε ότι ο Άπληστος Αλγόριθμος έχει καλύτερη επίδοση και στην κατηγορία των Ψευδοτυχαίων γραφημάτων η επίδοση των αλγορίθμων είναι παρόμοια.","The Steiner Forest Problem is a generalization of Steiner Tree and moreover the Minimum Spanning Tree problem. Those problems are widely known as combinatorial optimization problems. Furthermore, they found many applications such as the design of VLSI circuits, the design of telecommunication networks and the reconstruction of phylogenetic trees. Therefore, finding solutions to those problems means that we solve all practical problems connected to them. Karp had shown that the decision problem of Steiner Tree is NP-Complete. Thus, finding an optimal solution in polynomial time for that problem, consequently for the Steiner Forest Problem, is NP-Hard, so we should design approximation algorithms. For a long time the best known purely combinatorial algorithms did not have constant approximation ratios, and the only constant approximation ratio method was a primal - dual method. Recently, Gupta and Kumar have given us a 96-approximation algorithm, which is purely combinatorial. In the current dissertation, we are called to improve the analysis of this algorithm (called Gluttonous), as well as compare it to another non-constant approximation Greedy algorithm. We show that Gluttonous is a 2-approximation algorithm on Trees and implement the two algorithms so we can compare them on specific instances. In practise, the Greedy and Gluttonous algorithms are very close to an optimal solution for Tree instances, for Pseudo-random Graphs they have similar behaviour and for the case of Complete Graphs the Greedy algorithm outruns the Gluttonous."]},{"key":"dc:title","label":"Title","values":["Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Δάσους Steiner"]}]}],"canonical_facts":{"dc:creator":["Γιαχούδης Νικόλαος","Giachoudis Nikolaos"],"dc:date":["2017"],"dc:description":["Το πρόβλημα Δάσους Steiner είναι μία γενίκευση του προβλήματος Δέντρου Steiner και κατ’ επέκταση του Ελάχιστου Επικαλύπτοντος Δέντρου. Αυτά τα προβλήματα είναι ευρέως γνωστά προβλήματα συνδυαστικής βελτιστοποίησης. Επίσης, βρίσκουν πολλές εφαρμογές όπως, η σχεδίαση VLSI κυκλωμάτων, η σχεδίαση τηλεφωνικών δικτύων και η ανακατασκευή φυλογενετικών δέντρων. Επομένως, η μελέτη αυτών των προβλημάτων και η σχεδίαση αλγορίθμων, που τα επιλύουν, είναι σημαντική. Επιλύοντας τα γενικά προβλήματα επιλύουμε και όλα τα σχετικά πρακτικά προβλήματα. Έχει αποδειχθεί από τον Karp ότι το αντίστοιχο πρόβλημα απόφασης του Δέντρου Steiner, και κατ’ επέκταση του Δάσους Steiner, είναι NP-Πλήρες. Επομένως, το να βρούμε σε πωλυωνυμικό χρόνο τη βέλτιστη λύση είναι NP-Δύσκολο, το οποίο σημαίνει ότι θα πρέπει να σχεδιάσουμε προσεγγιστικούς αλγόριθμους. Για αρκετό χρονικό διάστημα οι καλύτεροι αλγόριθμοι συνδυαστικής φύσεως δεν είχαν κάποια σταθερή προσέγγιση, η μόνη 2-προσεγγιστική μέθοδος που είχαμε ήταν μια μέθοδος αρχικού - δυϊκού από την περιοχή του Γραμμικού Προγραμματισμού. Πρόσφατα, όμως, οι Gupta και Kumar μας έδωσαν έναν 96-προσεγγιστικό αλγόριθμο συνδυαστικής φύσεως. Καλούμαστε, λοιπόν, να βελτιώσουμε την ανάλυση αυτού του αλγόριθμου καθώς και να τον συγκρίνουμε με τον Άπληστο Αλγόριθμο, ο οποίος δεν έχει σταθερή προσέγγιση. Στην παρούσα διπλωματική εργασία δείξαμε ότι ο ”Αδηφάγος” Αλγόριθμος είναι 2-προσεγγιστικός στην κατηγορία των Δέντρων. Επίσης, πραγματοποιήθηκε μία υλοποίηση των δύο αλγορίθμων με σκοπό την πειραματική τους σύγκριση. Είδαμε ότι, οι δύο αλγόριθμοι βρίσκουν λύσεις πολύ κοντά στη βέλτιστη όσον αφορά τα Δέντρα, στην κατηγορία των Πλήρη γραφημάτων είδαμε ότι ο Άπληστος Αλγόριθμος έχει καλύτερη επίδοση και στην κατηγορία των Ψευδοτυχαίων γραφημάτων η επίδοση των αλγορίθμων είναι παρόμοια.","The Steiner Forest Problem is a generalization of Steiner Tree and moreover the Minimum Spanning Tree problem. Those problems are widely known as combinatorial optimization problems. Furthermore, they found many applications such as the design of VLSI circuits, the design of telecommunication networks and the reconstruction of phylogenetic trees. Therefore, finding solutions to those problems means that we solve all practical problems connected to them. Karp had shown that the decision problem of Steiner Tree is NP-Complete. Thus, finding an optimal solution in polynomial time for that problem, consequently for the Steiner Forest Problem, is NP-Hard, so we should design approximation algorithms. For a long time the best known purely combinatorial algorithms did not have constant approximation ratios, and the only constant approximation ratio method was a primal - dual method. Recently, Gupta and Kumar have given us a 96-approximation algorithm, which is purely combinatorial. In the current dissertation, we are called to improve the analysis of this algorithm (called Gluttonous), as well as compare it to another non-constant approximation Greedy algorithm. We show that Gluttonous is a 2-approximation algorithm on Trees and implement the two algorithms so we can compare them on specific instances. In practise, the Greedy and Gluttonous algorithms are very close to an optimal solution for Tree instances, for Pseudo-random Graphs they have similar behaviour and for the case of Complete Graphs the Greedy algorithm outruns the Gluttonous."],"dc:identifier":["uoadl:1722725","https://pergamos.lib.uoa.gr/uoa/dl/object/1722725"],"dc:language":["Ελληνικά","Greek"],"dc:subject":["Πληροφορική","Computer science"],"dc:title":["Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Δάσους Steiner"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:29:27Z"}