We consider the solution of matching problems with a convex cost function via a network flow algorithm. We review the general mapping between matching problems and flow problems on skew symmetric networks and revisit several results on optimality of network flows. We use these results to derive a balanced capacity scaling algorithm for matching problems with a linear cost function. The latter is later generalized to a balanced capacity scaling algorithm also for a convex cost function. We prove the correctness and discuss the complexity of our solution.
[1] W. Kocay and D. Stone, “Balanced Network Flows,” Bulletin of the Institute of Combinatorics and Its Applications, Vol. 7, No. 1, 1993, pp. 17-32.
[2] N. Appolonio and A. Sebo, “Minconvex Factors of Prescribed Size in Graphs,” Technical Report 145, Les Cahiers du Laboratoire Leibniz, 2006.
[3] A. Berger and W. Hochstattler, “Minconvex Graph Factors of Prescribed Size and a Simpler ′Reduction to Weighted f-Factors,” Electronic Notes in Discrete Mathematics, Vol. 28, 2007, pp. 69-76. doi:10.1016/j.endm.2007.01.011
[4] C. Fremuth-Paeger and D. Jungnickel. “Balanced Network Flows. I. A Unifying Framework for Design and Analysis of Matching Problems,” Networks, Vol. 33, No. 1, 1999, pp. 1-28. doi:10.1002/(SICI)1097-0037(199901)33:1<1::AID-NET1>3.0.CO;2-M
[5] B. Korte and J. Vygen, “Combinatorial Optimization,” Springer Verlag, New York, 2000. doi:10.1007/978-3-662-21708-5
[6] D. Jungnickel, “Graphs, Networks and Algorithms,” Springer Verlag, New York, 2004.
[7] C. Fremuth-Paeger, “Degree Constrained Subgraph Problems and Network Flow Optimization,” Wißner Verlag, Augsburg, 1997.
[8] C. Weber, “Minimum Cost Flow Grundlagen und Erste Algorithmen,” 2005.
http://www.informatik.uni-
trier.de/naeher/professur/courses/ws2005/exe
rcises/seminar/ausarbeitungweber.pdf
[9] D. Bertsekas, “Network Optimization: Continuous and Discrete Models,” Athena Scientific, Belmont, 1998.
[10] A. V. Goldberg and A. V. Karzanov, “Path Problems in Skew-Symmetric Graphs,” SODA: ACM Symposium on Discrete Algorithms, Arlington, 23-25 January 1994, pp. 526-535.
[11] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, “Network Flows: Theory, Algorithms and Applications,” Prentice Hall, 1993.