Network flows and network design in theory and practice

Front Cover
Jannik Matuschke, 2014 - 161 pages

Network flow and network design problems arise in various application areas of combinatorial optimization, e.g., in transportation, production, or telecommunication. This thesis contributes new results to four different problem classes from this area, providing models and algorithms with immediate practical impact as well as theoretical insights into complexity and combinatorial structure of network optimization problems: (i) We introduce a new model for tactical transportation planning that employs a cyclic network expansion to integrate routing and inventory decisions into a unified capacitated network design formulation. We also devise several algorithmic approaches to solve the resulting optimization problem and demonstrate the applicability of our approach on a set of real-world logistic networks. (ii) We present approximation algorithms for combined location and network design problems, including the first constant factor approximation for capacitated location routing. (iii) We derive a max-flow/min-cut theorem for abstract flows over time, a generalization of the well-known work of Ford and Fulkerson that restricts to a minimal set of structural requirements. (iv) We devise algorithms for finding orientations of embedded graphs with degree constraints on vertices and faces, answering an open question by Frank.


What people are saying - Write a review

We haven't found any reviews in the usual places.


Abstract flows over time
An integrated approach to tactical transportation planning
Approximating combined location and network design problems
Degreeconstrained orientations of embedded graphs
Notation index
Subject index

Common terms and phrases

Bibliographic information