Datenbestand vom 12. Dezember 2017
Tel: 089 / 66060798
Mo - Fr, 9 - 12 Uhr
Fax: 089 / 66060799
ALLE BESTELLUNGEN AB DEM 11.12. ERSCHEINEN IM JANUAR 2018.
aktualisiert am 12. Dezember 2017
978-3-8439-2410-8, Reihe Mathematik
Analyzing Infeasible Flow Networks
233 Seiten, Dissertation Technische Universität Darmstadt (2015), Softcover, B5
For general linear systems, there are mainly two concepts for infeasibility analysis: Irreducible infeasible subsystems (IISs) and IIS covers (IISCs). In this thesis, we study characteristics and aspects of computational complexity of IISs and IISCs in the special case of infeasible network flow problems with supplies and demands. Infeasible flow networks can be characterized via violated cut-inequalities of the classical Gale-Hoffman theorem. We show a one-to-one correspondence between IISs and those Gale-Hoffman-inequalities in which one side of the cut is weakly connected, as well as strong NP-hardness of finding an IIS of minimal cardinality in flow networks. Along the way, we present some generalizations to gas transportation networks and arbitrary linear systems. Apart from IIS covers, we also investigate the special case of covers which only contain flow bounds (arc covers) and settle their complexity. Moreover, we show inapproximability for minimum arc covers and highlight some polynomially solvable special cases. This leads to the development of two different fixed parameter algorithms. Based on the identified characteristics, we develop a number of heuristics to compute arc covers. These are surveyed regarding their suitability for practical application in computational experiments.