Κάλυψη συνόλου και βελτιστοποίηση δικτύων: δυναμικοί και προσεγγιστικοί αλγόριθμοι

Abstract

The dissertation concerns design and analysis of set covering and network optimization algorithms.The content of the dissertation consists of three parts: Probabilistic Set Covering, Dynamic GraphAlgorithms, and Network Optimization. For the set covering problem we study the behavior of asimple algorithm in the most general probabilistic model for the problem. We show that this algorithmis asymptotically optimum in expectation with a small variance of the produced solution values. Thisresults are extended for the case of the well known greedy algorithm for set covering. We also studyrobustness of feasible solutions in the same model. In the second part we design algorithms foroptimization problems on dynamic undirected networks with connectivity constraints and develop thefirst dynamic algorithm for the directed minimum spanning tree problem on directed graphs. Finally,we study two representative network optimization problems: we develop a game-theoretic analysisfor the object placement problem over a network, and design approximation algorithms for theSteiner tree problem in the presence of input uncertainty.

Η διατριβή αφορά σε σχεδίαση και ανάλυση αλγορίθμων για το πρόβλημα κάλυψης συνόλου και γιαπροβλήματα βελτιστοποίησης δικτύων. Το περιεχόμενο της διατριβής χωρίζεται θεματικά σε τρίαμέρη: Πιθανοτική Κάλυψη Συνόλου, Δυναμικοί Αλγόριθμοι Γράφων, και Βελτιστοποίηση Δικτύων. Γιατο πρόβλημα κάλυψης συνόλου αναλύουμε τη συμπεριφορά ενός απλού αλγορίθμου στο γενικότεροπιθανοτικό μοντέλο για το πρόβλημα. Δείχνουμε ότι ο αλγόριθμος αυτός είναι βέλτιστος κατάαναμενόμενη τιμή με μικρή διασπορά στις τιμές των λύσεων που παράγει. Τα αποτελέσματα αυτάεπεκτείνονται στην περίπτωση του διαδεδομένου άπληστου αλγόριθμου για το πρόβλημα. Επιπλέονμελετούμε την ευρωστία εφικτών λύσεων στο συγκεκριμένο πιθανοτικό μοντέλο. Στο δεύτερο μέροςσχεδιάζουμε αλγορίθμους για προβλήματα βελτιστοποίησης δυναμικών μη κατευθυνόμενων δικτύωνμε περιορισμούς συνδεσιμότητας και αναπτύσσουμε τον πρώτο δυναμικό αλγόριθμο για τοπρόβλημα κατευθυνόμενου επικαλυπτικού δέντρου ελάχιστου κόστους σε κατευθυνόμενουςγράφους. Τέλος, μελετούμε δύο αντιπροσωπευτικά προβλήματα βελτιστοποίησης δικτύων:αναπτύσσουμε μια παιγνιοθεωρητική ανάλυση για το πρόβλημα τοποθέτησης αντικειμένων σε έναδίκτυο, και σχεδιάζουμε προσεγγιστικούς αλγορίθμους για το πρόβλημα Steiner δέντρου ελάχιστουκόστους σε συνθήκες αβεβαιότητας των δεδομένων εισόδου.