Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)
Πληροφορική

2017-07-17

2017

Giachoudis Nikolaos

Βασίλης Ζησιμόπουλος, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών

Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Δάσους Steiner

Greek

Approximation Algorithms for the Steiner Forest Problem

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.

Computer science

Approximation Algorithms, Steiner Forest, Steiner Tree, Graph Theory, Combinatorial Optimization

Yes

6

Yes

24

74

https://pergamos.lib.uoa.gr/uoa/dl/object/1722725/file.pdf

https://pergamos.lib.uoa.gr/uoa/dl/object/1722725