Multicriteria Approximation of Network Design and Network Upgrade Problems

Network planning has come to great importance during the past decades. Today's telecommunication, traffic systems, and logistics would not have been evolved to the current state without careful analysis of the underlying network problems and precise implementation of the results obtained from those examinations. Graphs with node and arc attributes are a very useful tool to model realistic applications, while on the other hand they are well understood in theory. We investigate network design problems which are motivated particularly from applications in communication networks and logistics. Those problems include the search for homogeneous subgraphs in edge labeled graphs where either the total number of labels or the reload cost are subject to optimize. Further, we investigate some variants of the dial a ride problem. On the other hand, we use node and edge upgrade models to deal with the fact that in many cases one prefers to change existing networks rather than implementing a newly computed solution from scratch. We investigate the construction of bottleneck constrained forests under a node upgrade model, as well as several flow cost problems under a edge based upgrade model. All problems are examined within a framework of multi-criteria optimization. Many of the problems can be shown to be NP-hard, with the consequence that, under the widely accepted assumption that P is not equal to NP, there cannot exist efficient algorithms for solving the problems. This motivates the development of approximation algorithms which compute near-optimal solutions with provable performance guarantee in polynomial time.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Würzburg

Year

2001

Author dc:creator

• Wirth, Hans-Christoph

Contributors dc:contributor

• Noltemeier, Hartmut

• network design
• network upgrade
• approximation algorithms
• edge labeled graphs
• reload cost
• spanning tree
• dial a ride
• constrained forest

Repository record source_url

https://opus.bibliothek.uni-wuerzburg.de/frontdoor/index/index/docId/237

OAI identifier oai:identifier

oai:opus.bibliothek.uni-wuerzburg.de:237