National and Kapodistrian University of Athens
Κάλυψη συνόλου και βελτιστοποίηση δικτύων: δυναμικοί και προσεγγιστικοί αλγόριθμοι
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2006
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Telelis, Orestis
- Τελέλης, Ορέστης
Subjects
dc:subject × 13Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/22196