Back to search

National and Kapodistrian University of Athens

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

Abstract

dc:description

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.

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 × 13

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/22196

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Telelis, Orestis; Τελέλης, Ορέστης. Κάλυψη συνόλου και βελτιστοποίηση δικτύων: δυναμικοί και προσεγγιστικοί αλγόριθμοι. National and Kapodistrian University of Athens, 2006. http://hdl.handle.net/10442/hedi/22196