Open Journal of Discrete Mathematics

Volume 3, Issue 3 (July 2013)

ISSN Print: 2161-7635   ISSN Online: 2161-7643

Google-based Impact Factor: 0.76  Citations  h5-index & Ranking

Balanced Min Cost Flow on Skew Symmetric Networks with Convex Costs

HTML  Download Download as PDF (Size: 327KB)  PP. 155-161  
DOI: 10.4236/ojdm.2013.33028    3,453 Downloads   5,288 Views  
Author(s)

ABSTRACT

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.

Share and Cite:

H. Soller, "Balanced Min Cost Flow on Skew Symmetric Networks with Convex Costs," Open Journal of Discrete Mathematics, Vol. 3 No. 3, 2013, pp. 155-161. doi: 10.4236/ojdm.2013.33028.

Cited by

No relevant information.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.