{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2779536"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2779536","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Ισορροπία Αγοράς με Γραμμικές Αντικειμενικές Συναρτήσεις","abstract":"Αντικείμενο μελέτης αυτής της εργασία είναι το πρόβλημα του υπολογισμού Ισορροπιών σε αγορές Arrow- Debreu και Fisher με γραμμικές αντικειμενικές συναρτήσεις. Στο πρώτο μέρος, παρουσιάζονται πολυωνυμικοί αλγόριθμοι για το πρόβλημα με την χρήση κυρτών προγραμμάτων βελτιστοποίησης. Οι αλγόριθμοι αυτοί έχουν το μειονέκτημα ότι στηρίζονται στον ελλειψοειδή αλγόριθμο, ο οποίος δεν είναι αποδοτικός στην πράξη και για τον λόγο αυτό τα τελευταία χρόνια έχει επιχειρηθεί η σχεδίαση αλγορίθμων που βασίζονται σε συνδυαστικές μεθόδους, όπως για παράδειγμα ο υπολογισμός της μέγιστης ροής σε ένα γράφημα. Το δεύτερο μέρος αυτής της εργασίας επικεντρώνεται σε αλγορίθμους τέτοιας φύσης. Αρχικά, παρουσιάζεται ένας ισχυρά πολυωνυμικός αλγόριθμος για αγορές Fisher και, αφού εξηγηθούν οι κύριες τεχνικές που χρησιμοποιεί, αναλύεται η πολυπλοκότητά του. Στη συνέχεια, στο τελευταίο τμήμα της εργασίας, οι τεχνικές αυτές επεκτείνονται και χρησιμοποιούνται για την κατασκευή ενός ασθενώς πολυωνυμικού συνδυαστικού αλγορίθμου για αγορές Arrow-Debreu.","abstract_html":"Αντικείμενο μελέτης αυτής της εργασία είναι το πρόβλημα του υπολογισμού Ισορροπιών σε αγορές Arrow- Debreu και Fisher με γραμμικές αντικειμενικές συναρτήσεις. Στο πρώτο μέρος, παρουσιάζονται πολυωνυμικοί αλγόριθμοι για το πρόβλημα με την χρήση κυρτών προγραμμάτων βελτιστοποίησης. Οι αλγόριθμοι αυτοί έχουν το μειονέκτημα ότι στηρίζονται στον ελλειψοειδή αλγόριθμο, ο οποίος δεν είναι αποδοτικός στην πράξη και για τον λόγο αυτό τα τελευταία χρόνια έχει επιχειρηθεί η σχεδίαση αλγορίθμων που βασίζονται σε συνδυαστικές μεθόδους, όπως για παράδειγμα ο υπολογισμός της μέγιστης ροής σε ένα γράφημα. Το δεύτερο μέρος αυτής της εργασίας επικεντρώνεται σε αλγορίθμους τέτοιας φύσης. Αρχικά, παρουσιάζεται ένας ισχυρά πολυωνυμικός αλγόριθμος για αγορές Fisher και, αφού εξηγηθούν οι κύριες τεχνικές που χρησιμοποιεί, αναλύεται η πολυπλοκότητά του. Στη συνέχεια, στο τελευταίο τμήμα της εργασίας, οι τεχνικές αυτές επεκτείνονται και χρησιμοποιούνται για την κατασκευή ενός ασθενώς πολυωνυμικού συνδυαστικού αλγορίθμου για αγορές Arrow-Debreu.","abstract_has_math":false,"creators":["Καραθάνος Χρήστος","Karathanos Christos"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-11-19T05:31:57Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2779536"],"render_values":[{"text":"uoadl:2779536","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2779536","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2779536","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%3A2779536","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Καραθάνος Χρήστος","Karathanos Christos"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018"]},{"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":["Θετικές Επιστήμες","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:2779536","https://pergamos.lib.uoa.gr/uoa/dl/object/2779536"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Αντικείμενο μελέτης αυτής της εργασία είναι το πρόβλημα του υπολογισμού Ισορροπιών σε αγορές Arrow- Debreu και Fisher με γραμμικές αντικειμενικές συναρτήσεις. Στο πρώτο μέρος, παρουσιάζονται πολυωνυμικοί αλγόριθμοι για το πρόβλημα με την χρήση κυρτών προγραμμάτων βελτιστοποίησης. Οι αλγόριθμοι αυτοί έχουν το μειονέκτημα ότι στηρίζονται στον ελλειψοειδή αλγόριθμο, ο οποίος δεν είναι αποδοτικός στην πράξη και για τον λόγο αυτό τα τελευταία χρόνια έχει επιχειρηθεί η σχεδίαση αλγορίθμων που βασίζονται σε συνδυαστικές μεθόδους, όπως για παράδειγμα ο υπολογισμός της μέγιστης ροής σε ένα γράφημα. Το δεύτερο μέρος αυτής της εργασίας επικεντρώνεται σε αλγορίθμους τέτοιας φύσης. Αρχικά, παρουσιάζεται ένας ισχυρά πολυωνυμικός αλγόριθμος για αγορές Fisher και, αφού εξηγηθούν οι κύριες τεχνικές που χρησιμοποιεί, αναλύεται η πολυπλοκότητά του. Στη συνέχεια, στο τελευταίο τμήμα της εργασίας, οι τεχνικές αυτές επεκτείνονται και χρησιμοποιούνται για την κατασκευή ενός ασθενώς πολυωνυμικού συνδυαστικού αλγορίθμου για αγορές Arrow-Debreu.","This thesis focuses on the problem of finding Equilibria in Arrow-Debreu and Fisher markets with Linear Utilities. In the first part, we present polynomial time algorithms via convex programming. Such algorithms use the Ellipsoid algorithm as a black box and are notoriously non-practical, therefore, there has recently been a lot of effort towards obtaining algorithms through the use of combinatorial tools, such as flow computation in graphs. In the second part, we focus on algorithms of such nature. First, we present a strongly polynomial algorithm for Fisher Markets and after highlighting the main techniques used by it we analyze its complexity. Finally, we focus on extensions of those techniques that lead to the development of a weakly-polynomial combinatorial algorithms for Arrow-Debreu markets with Linear utilies."]},{"key":"dc:title","label":"Title","values":["Ισορροπία Αγοράς με Γραμμικές Αντικειμενικές Συναρτήσεις"]}]}],"canonical_facts":{"dc:creator":["Καραθάνος Χρήστος","Karathanos Christos"],"dc:date":["2018"],"dc:description":["Αντικείμενο μελέτης αυτής της εργασία είναι το πρόβλημα του υπολογισμού Ισορροπιών σε αγορές Arrow- Debreu και Fisher με γραμμικές αντικειμενικές συναρτήσεις. Στο πρώτο μέρος, παρουσιάζονται πολυωνυμικοί αλγόριθμοι για το πρόβλημα με την χρήση κυρτών προγραμμάτων βελτιστοποίησης. Οι αλγόριθμοι αυτοί έχουν το μειονέκτημα ότι στηρίζονται στον ελλειψοειδή αλγόριθμο, ο οποίος δεν είναι αποδοτικός στην πράξη και για τον λόγο αυτό τα τελευταία χρόνια έχει επιχειρηθεί η σχεδίαση αλγορίθμων που βασίζονται σε συνδυαστικές μεθόδους, όπως για παράδειγμα ο υπολογισμός της μέγιστης ροής σε ένα γράφημα. Το δεύτερο μέρος αυτής της εργασίας επικεντρώνεται σε αλγορίθμους τέτοιας φύσης. Αρχικά, παρουσιάζεται ένας ισχυρά πολυωνυμικός αλγόριθμος για αγορές Fisher και, αφού εξηγηθούν οι κύριες τεχνικές που χρησιμοποιεί, αναλύεται η πολυπλοκότητά του. Στη συνέχεια, στο τελευταίο τμήμα της εργασίας, οι τεχνικές αυτές επεκτείνονται και χρησιμοποιούνται για την κατασκευή ενός ασθενώς πολυωνυμικού συνδυαστικού αλγορίθμου για αγορές Arrow-Debreu.","This thesis focuses on the problem of finding Equilibria in Arrow-Debreu and Fisher markets with Linear Utilities. In the first part, we present polynomial time algorithms via convex programming. Such algorithms use the Ellipsoid algorithm as a black box and are notoriously non-practical, therefore, there has recently been a lot of effort towards obtaining algorithms through the use of combinatorial tools, such as flow computation in graphs. In the second part, we focus on algorithms of such nature. First, we present a strongly polynomial algorithm for Fisher Markets and after highlighting the main techniques used by it we analyze its complexity. Finally, we focus on extensions of those techniques that lead to the development of a weakly-polynomial combinatorial algorithms for Arrow-Debreu markets with Linear utilies."],"dc:identifier":["uoadl:2779536","https://pergamos.lib.uoa.gr/uoa/dl/object/2779536"],"dc:language":["Ελληνικά","Greek"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Ισορροπία Αγοράς με Γραμμικές Αντικειμενικές Συναρτήσεις"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:31:57Z"}