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.

1. Introduction

Skew symmetric networks have become an important tool for the efficient solution of matching problems [1]. Going over from a matching problem to a problem of flow optimization often allows for simplification and speed-up of solution algorithms. Typical matching problems do not only include maximizing a matching but often additionally minimizing the costs for the participants involved. Typical examples include minconvexproblems as studied in [2,3]. For such minconvex problems a convex function in the number of matchings has to be minimized for each participant. So far the solution of such problems using skew symmetric networks has not been demonstrated.

In this paper we therefore consider the problem of minimizing a separable convex objective function over a skew-symmetric network with a balanced flow. This problem can be mapped on the aforementioned matching problems and allows for an efficient solution of the latter. Specifically, we will derive a balanced capacity scaling algorithm incorporating the additional problem of a convex cost function.

In Section 2 we will shortly review skew symmetric networks and their connection to matchings. Section 3 will be devoted to a short summary of necessary results for optimality. In Section 4 we will present the balanced capacity scaling algorithm for a linear cost function going over in Section 5 to the description of the algorithm for a convex cost function. In Section 6 we will discuss some possible improvements of the aforementioned algorithm. We will conclude and sum up our results in Section 7.

2. Skew Symmetric Networks and Matchings

A graph is a pair of disjoint, finite sets E and V corresponding to the edges and vertices of the graph. If the edges between vertices are directed we have a directed graph. This allows for the definition of a network.

Definition: network Let be a directed graph and two functions. We call the triplet a network and the functions v and w the upper and lower capacity bound.

Definition: skew symmetric network [4]

A skew symmetric network is a network with the following properties

-  the vertices of N contain a source s and a drain t and two sets of vertices and such that a bijection exist.

-  N contains edges

-  the other edges appear pairwise between X and meaning if exist then so does and vice versa

-  the capacities obey

and for all edges in the network Definition: flownetwork [5, p. 154]

Let N be a network and s and t are vertices in such that s is connected to t via edges in. A flow is a mapping. If a flow is defined on N the network is called a flow network.

The flow on the network should later allow to map it to a matching. Therefore additional constraints are necessary. The excess is defined as

(1)

This allows to define an admissible flow.

Definition: admissible A flow on a network is admissible if and.

Definition: balanced A flow on a skew symmetric network is balanced if and for all loops is even.

An admissible flow can always be turned into a circulation, meaning a flow where no excess is found on any vertex. We just have to introduce a vertex from t to s which has a flow value of. Consequently is does not matter whether we consider circulation problems or flows.

Admissible and balanced flows correspond to matchings that we want to define below.

Definition: matching [6, p. 213]

Let be a graph, , . A graph with is called a matching if at least edges and at most edges in M are incident with the vertex i in V and for every i is incident with j at least times and at most times.

Theorem: correspondence Every balanced admissible flow on a skew symmetric network corresponds to a matching on the corresponding graph with

.

Proof: in [7], pp. 35-36 This correspondence is illustrated in Figure 1 showing a graph with a matching and the corresponding skew symmetric flow network.

This first section summarized the previously known results on the correspondence between matchings and flow optimization which allows for efficient algorithms [5, p. 207].

3. Optimality of Network Flows

Since we have now reviewed the mapping between matchings and network flows we want to state several important results on the optimality of network flows which can be directly carried over. e.g. a maximal admissible balanced flow on the skew symmetric network corresponds to a maximal matching [7]. We start with the following definition.

Definition: restnetwork [7, p. 21]

Let N be a flownetwork and x the flow on it. Then the residual capacity corresponding to x is given by:

(2)

is the backward edge, when the flow is negative. The edges with together with the vertices that coincide with an edge form the restnetwork.

So far we have only introduced the correspondence of network flows and matchings. However, we want to compute optimal matchings with respect to a cost function. This means that we have to consider problems on networks N of the type

(3)

The additional complication compared to maximum balanced flow problems is the cost function. Therefore we want to introduce the necessary framework in order to deal with it. We start by the following

Definition: potential, reduced costs [8]

The potential function associates with each vertex a number, the potential i.

The reduced costs of an edge are defined as.

The length of a path is then obviously defined as the sum of the reduced costs of the individual edges. The shortest valid path between two points in a network connects the two points via a valid path and the path has minimum length.

Corollary: [8]

For the reduced costs on a network N any path p from a vertex k to a vertex l fulfills

(4)

and for any circle K

(5)

Obviously we shouldn’t try to find a solution by enhancing or decreasing the flow on arbitrary edges but we need a good measure for distance.

Definition: skew symmetric distances Let P_i,j be the set of admissible paths in the restnetwork with start-node and endnode. Then we define the skew symmetric distance from i to j as

(6)

We call the distance to s and the corresponding function is called d.

Definition: symmetric distances Let d be the set of skew symmetric distances on a flow network N then the symmetric distances are given by The corresponding set is denoted by sd.

(7)

At this point we state a theorem that has been extensively used for proving optimality Theorem: Reduced Cost Optimality [8]

Let x be an admissible flow then x is optimal if a potential π exists such that for all edges in the restnetwork

. (8)

The potential π is often called the dual solution. It also has a practical importance [9]. Let us assume we have a logistics company with several warehouses. The transport costs per unit load between the different warehouses correspond to the costs on the edges. Then the potential for an optimal solution corresponds to the costs per unit load for storing them in a warehouse.

We need two further lemmas concerning the optimality of network flows

wang#title3_4:spLemma:

Let x be a balanced flow on a network N that fulfills the reduced cost optimality with respect to a potential π. Furthermore sd denotes the symmetric distances with respect to the reduced costs then i) the flow x fulfills the reduced cost optimality also with respect to the potential

ii) the reduced costs are zero on the shortest valid paths p and p’.

wang#title3_4:spProof:

We prove both statements one after the other:

i) Since x fulfills the reduced cost optimality . Furthermore since sd is calculated from the shortest valid paths we know:

(9)

We use the definition of the reduced costs

(10)

ii) Let p be an st path and p' its bijection. For every edge (ij) in p, we have. The same holds for the bijection. Therefore we have

(11)

wang#title3_4:spLemma:

Assume a flow x fulfills the reduced cost optimality on a flow network N. If we change the flow both on the shortest valid path p and its bijection p' by

(12)

we find a new flow x' which also fulfills the reduced cost optimality with respect to the potential.

wang#title3_4:spProof:

From the lemma above we know that the reduced costs are zero on p and p' with respect to π'. Therefore the reduced cost optimality cannot be violated if we enhance the flow by the maximum allowed capacity as defined above.

Obviously, an important ingredient is the solution of the shortest valid path problem. This has been discussed in detail in [10] and its complexity is, where m is the number of edges and n is the number vertices in the network.

We now get to the combination of the results of Section 2 and 3 being an algorithm to compute optimal flows on skew-symmetric networks.

4. Balanced Capacity Scaling

In this Section we describe the balanced capacity scaling algorithm for a linear cost function as in Equation (3) with the additional assumption that the costs are always positive. We will later generalize our result to a convex cost function. The idea of capacity scaling is to look at subgraphs in the restnetwork with some minimum capacity and to optimize the flow on these subgraphs successsively.

We denote this minimum capacity by Δ and we call each phase of the algorithm where Δ does not change a Δ-scaling phase. We define two sets

(13)

We can first calculate the maximum balanced flow through the network using one of the algorithms in [7] and use the result b as. We now begin the algorithm with flow 0 and potential 0 such that the reduced cost optimality is fulfilled but the flow does not fulfill Equation (3) as far as the excess is concerned.

For correctly prescribed Δ initially

. We define and start with. This is the largest U such that not initially. Furthermore we define

(14)

We additionally need the following Definition: Δ-restnetwork The Δ-restnetwork is defined as the network formed when only taking the edges in a flownetwork N into account with. If the original flow network was skew symmetric, obviously also is skew symmetric.

We now denote the balanced capacity scaling algorithm and afterwards prove its correctness. We state the algorithm in a form close to typical programming language.

begin

while do begin for every edge in the Δ-restnetwork do if then increase flow on by

increase flow on by

recalculate the e(i)’s

while do begin take a vertex

calculate the shortest path from l to k in

or connect the two with an edge

enhance the flux by

units on p and

update

end;

end;

end;

Theorem:

The balanced capacity scaling algorithm calculates a maximal flow x on a skew symmetric network N with minimal costs.

Proof:

We prove the theorem by induction in the Δ-scaling phases.

In the beginning we have so that the reduced cost optimality is fulfilled. The network is skew symmetric in the beginning.

Now we assume the solution to be optimal in the 2Δ- scaling phase and go over to the Δ-scaling phase. New edges added in the Δ-scaling phase may have negative reduced costs. For them holds and we can enhance the flow on them by since the costs are negative. In this case they are not part of the Δ-restnetwork. Since the same has to hold for the bijection the network will be skew symmetric again. Consequently the reduced cost optimality is fulfilled after the first part.

In the second part we enhance the flow on shortest valid paths so that the reduced cost optimality will be fulfilled. If an edge is introduced with costs the costs are so high that the edge will not be part of the final solution.

We only need to show that the algorithm obtains an admissible flow for Δ < 1. However, for Δ < 1 no vertex can exists with an excess greater than one. However, due to the correspondence theorem the problem can only have integer flow variations so that no vertex with an excess smaller than one can exist.

Therefore we have found an optimal solution which has to be maximal since e(s) was assumed to be the maximal flow through the network.

We therefore have an algorithm to solve the Balanced Min Cost Flow Problem on skew symmetric networks. In the next section we want to discuss the additional complication of a problem with a convex cost functions.

5. Convex Costs

We first define the generalization of the problem in Equation (3) with a convex cost function:

(15)

The function is a mapping from into the real numbers and we know that for all

(17)

For a balanced capacity scaling algorithm for the problem in Equation (15) we follow [11, pp. 556-560].

The idea is to approximate the convex cost function by linear interpolation. This interpolation can be improved step by step until it is exact for all integer values as illustrated in Figure 2.

In the figure in each step we double the number of points in between which we assume the function to be constant. The frequency polygon therefore becomes a better approximation of the original function until we approximate the function at each integer value.

Since only integer flow values need to be considered the solution will be exact. In every Δ-scaling phase only changes of the flow values by need to be considered. Therefore we define the capacity and cost function for a Δ-scaling phase as:

(18)

In the previous algorithm we additionally defined c_max which we have to do here as well. No edge in the network can have costs of:

(19)

is chosen again to be the maximum flow value through the network. We denote now the algorithm and prove its correctness for solving problems of the type as in Equation (15) afterwards.

begin

while do begin for every edge in the Δ-restnetwork do if then increase flow on and on by Δ

if then reduce flow on and on by Δ

recalculate the e(i)’s

while do begin take a vertex

calculate the shortest path from l to k in

or connect the two with an edge with costs

enhance the flux by

units on p and p’

update and the reduced costs end;

end;

end;

We have to prove that the algorithm is correct.

Theorem:

The balanced capacity scaling algorithm calculates a maximal flow x on a skew symmetric network with a convex cost function with minimal costs.

Proof:

We first show that the conversion of the problem into the algorithm is correct. In the beginning and so that not more than Δ flow units can be shifted in the first phase. Due to the choice of Δ this holds also for the next Δ-scaling phases . Consequently it is sufficient to only consider changes of the flow by.

We now have to show that the reduced cost optimality is always fulfilled. In the beginning we have

(20)

so that the reduced cost optimality is fulfilled.

Now let us assume that x is the flow after the -scaling phase. We have the following cases for the flow in the Δ-scaling phase: i):, ii) , iii), iv).

The case iv) cannot occur for a convex cost function since we would have

(21)

However, from the definition of a convex cost function we know

(22)

and we have the disagreement.

The case i) fulfills the reduced cost optimality and we are left with ii) and iii). In case ii) we resolve this issue by enhancing the flow by Δ flow units. After the 2Δ- scaling phase we have

(23)

and we have

(24)

From the inequality from the 2Δ-scaling phase follows

(25)

and the inequality follows since the last line of Equation (25) is smaller than zero by Equation (24) and consequently Equation (23) follows.

The reduced costs have to be identical on since the network is skew symmetric. We can treat case iii) completely analogous.

Everything we still need to show is that the reduced cost optimality is also fulfilled if we enhance the flow by and not by Δ. We consider and we obtain for the reduced costs

(26)

Consequently the reduced cost optimality is still fulfilled. The same can be shown for the edge.

At the end we will therefore obtain an admissible flow which is the solution to the Min Cost Flow Problem on a skew symmetric network with a convex cost function.

We will finally get to the complexity of this problem using the above algorithm.

Theorem

The balanced capacity scaling algorithm has a complexity of with the complexity of computing a shortest valid path.

Proof:

At the end of each 2Δ-scaling phase we have or so that at most there is of flow that can be shifted along in the next phase. Additionally we change the flow at the beginning of the Δ- scaling phase by at most so that the total excess can be at most. In every iteration at least flow units are shifted so that we will have at most iterations of the shortest valid path algorithm so that the complexity is. We can have at most phases so that the complexity follows.

6. Possible Improvements

One can still improve the above algorithm by noticing that for there can be no edge with. In this case shortest paths in the network are always valid and we can use the simpler Dijkstra algorithm for shortest paths. An implementation with Fibonacci heaps has complexity (see [11]) so that one only has to use the more involved shortest valid path algorithm in the last phase.

The author has also tried to implement other methods used in networks with a convex cost function like the Out-of-Kilter algorithm, the Relaxation Algorithm, Cancel-and-Tighten and the primal-dual algorithm. Inspite of the noticeable simplicity of the above algorithm none of the above provided real improvements in terms of complexity for the solution so that only the Balanced Capacity Scaling algorithm is presented here.

7. Conclusion

We have presented the first solution and complexity analysis of the Min Cost Flow Problem on a skew symmetric network with a convex cost function. The solution of this problem is of special relevance for the solution of matching problems with a convex cost function. The solution is based on a balanced capacity scaling algorithm.

8. Acknowledgements

The author would like to thank D. Reeb and I. Deppner for many helpful comments.

REFERENCES