TITLE:
Balanced Min Cost Flow on Skew Symmetric Networks with Convex Costs
AUTHORS:
Henning Soller
KEYWORDS:
Matching; Skew Symmetric Network; Convex Cost Function; Optimization
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.3 No.3,
July
12,
2013
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.