
PDF, German
Download (2MB)  Terms of use 
Abstract
Standard matching problems can be stated in terms of skew symmetric networks. On skew symmetric networks matching problems can be solved using network flow techniques. We consider the problem of minimizing a separable convex objective function over a skewsymmetric network with a balanced flow. We call this problem the Convex Balanced Min Cost Flow (Convex BMCF) problem. We start with 2 examples of Convex BMCF problems. The first problem is a problem from condensed matter physics: We want to simulate a so called superrough phase using methods from graphtheory. This problem has previously been studied by Blasum, Hochstaettler, Rieger a and Moll. The second problem is a typical example for the minconvexproblems previously studied by Apollonio and Sebo and Berger and Hochstaettler [9]. We review the results for skewsymmetric networks by Jungnickel and FremuthPaeger and Kocay and Stone. Using these results we present several algorithms to solve the Convex BMCF problem. We present the first complete version of the PrimalDual algorithm previously studied by FremuthPaeger and Jungnickel. However, we only consider the case of positive costs. We also show how to apply this algorithm to the Convex BMCF problem. Then we extend the Shortest Admissible Path Approach of Jungnickel and FremuthPaeger [23, p. 12] to a complete algorithm for linear as well as convex cost problems on skew symmetric networks. In the same manner we show how to adapt the Capacity Scaling algorithm by Ahuja and Orlin to skew symmetric networks and balanced flows. The capacity scaling algorithm is weakly polynomial. Another possibility for a weakly polynomial algorithm is the Balanced OutofKilter algorithm. This algorithm is based on Fulkerson’s OutofKilter algorithm and Minoux’s adaptation of the algorithm for convex costs. We show that augmentation on valid paths is not always necessary and introduce the idea of slightly different networks. Using the same ideas for the Balanced Capacity Scaling we obtain an Enhanced Capacity Scaling algorithm. The Enhanced Capacity Scaling algorithm as well as the Balanced OutofKilter algorithm are the fastest algorithms presented here with a complexity of roughly O(m2log2U). Finally we show how to solve the problem from condensed matter physics using the new idea of antibalanced flows on skewsymmetric networks. Using the Balanced Successive Shortest Path algorithm we also obtain a new complexity limit for the minconvex problem. This improves the complexity bound of Berger [8] by a factor of m in the case of separable convex costs with positive slope. In the appendix of this thesis we consider dual approaches for the Convex BMCF problem. The Balanced Relaxation algorithm, based on the Relaxation algorithm by Bertsekas [13], does not determine a balanced flow as the resulting flow will not necessarily be integral. This way we only determine fractional matchings. As the algorithm is also slow this algorithm is probably of limited use. A better ansatz seems to be the Cancel and Tighten method by Karzanov and McCormick. We review their results and end with some ideas on how to implement a balanced version of this algorithm.
Item Type:  Master's thesis 

Supervisor:  Hochstaettler, Prof. Dr. Winfried 
Date of thesis defense:  3 September 2007 
Date Deposited:  03 Jun 2013 07:52 
Date:  2007 
Faculties / Institutes:  The Faculty of Mathematics and Computer Science > Department of Applied Mathematics 