<div class="csl-bib-body">
<div class="csl-entry">Ruthmair, M. (2012). <i>On solving constrained tree problems and an adaptive layers framework</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-54456</div>
</div>
In this thesis we consider selected combinatorial optimization problems arising in the field of network design. In many of these problems there is a central server sending out information to a set of recipients. A common objective is then to choose connections in the network minimizing the total costs. Besides this, current applications, e.g. in multimedia, usually ask for additional quality-of-service constraints, e.g. limiting the communication delay between the central server and the clients. In general, these problems can be modeled on a graph and in many cases an optimal solution corresponds to a rooted tree with minimum costs satisfying all the given constraints. The most relevant of these optimization problems are NP-hard and thus - provided that P is not equal to NP - it is usually not possible to obtain proven optimal solutions for medium- to large-sized problem instances. Therefore, heuristic approaches yielding high quality but in general sub-optimal solutions are of high practical interest. We present sophisticated preprocessing methods to reduce the problem size and new heuristic as well as exact state-of-the-art solution approaches for several of these optimization problems. The proposed heuristics include several construction and improvement methods embedded in various metaheuristics. Small- to medium-sized problem instances are tackled with exact algorithms, mostly concentrating on mathematical programming methods. We compare different modeling approaches, among them a transformation to a layered graph. Finally, we introduce a generally-applicable iterative adaptive layers framework which tries to partly overcome major computational issues of layered graph approaches.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
kombinatorische Optimierung
de
dc.subject
Netzwerkdesign
de
dc.subject
beschränkte Baumprobleme
de
dc.subject
Metaheuristiken
de
dc.subject
ganzzahlige lineare Programmierung
de
dc.subject
combinatorial optimization
en
dc.subject
network design
en
dc.subject
constrained tree problems
en
dc.subject
metaheuristics
en
dc.subject
integer linear programming
en
dc.title
On solving constrained tree problems and an adaptive layers framework
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Mario Ruthmair
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Pferschy, Ulrich
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen