Matchings Tidbit

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York 11451


Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)


Suppose we are given m workers and n jobs. For each worker one can specify which of the jobs the worker is qualified for. What is the maximum number of workers that can be assigned to a job for which the worker is qualified?

One can construct a graph theory model for this situation by constructing a graph with two sets of vertices, one representing the workers and one representing the jobs. In the diagram below (Figure 1), the worker vertices are shown at the top and the job vertices are shown at the bottom.

Figure 1

In this example, m = n = 7. In the graph model, a matching is a disjoint set of edges. One can look for a matching with a specified number of edges, a matching for which no additional edges can be added (such a matching is known as a maximal matching), or a matching which includes all of the vertices of the graph. When a matching includes all the vertices of a graph it is known as a perfect matching, and a necessary condition for this to happen is that the graph have an even number of vertices.

In Figure 1 it is easy to see that there is no perfect matching (despite there being an even number of vertices) because the workers who are represented by the vertices in the top row on the far left and far right collectively only are suited for doing 1 job, so they can not be assigned distinct jobs. Finding matchings in bipartite graphs (e.g. graphs for which the vertices can be divided into two sets so that there are no edges between vertices within each of the sets), such as the graph in Figure 1, is related to a problem concerning sets that was resolved by the British group theorist Philip Hall. The problem can be stated in these terms. Suppose we have a finite collection of sets X whose elements are drawn from a finite set Y. We allow for the case where some of the sets in X might be identical. Think of the sets in X's as committees whose members are people in the set Y. Is it possible to select a chairperson for each of the committees in such a manner that all the committee chairpeople are distinct? When such a collection of chairpeople can be selected we say that the sets in X have a system of distinct representatives or SDR. Hall proved the remarkable theorem that a collection of sets X has a system of distinct representatives if and only if the union of any k of the sets in X have at least k elements of Y.

Hall's Theorem is very elegant but it does not provide a polynomial time algorithms because to check the Hall condition requires an exponential number of checks. A polynomial time algorithm is given by Dénes König's alternating paths algorithm.

An extension of the model above assigns each edge in the matching a weight. In the worker-job situation this weight might represent a variety of different things. It might represent the time for the worker to complete the job, an efficiency score for the worker doing this job, a satisfaction score for the worker doing this job, etc. One can represent this information in graph form as in Figure 1 with weights on the edges or one can display the information in a table as shown in Figure 2.

Figure 2

The workers are named with small letters and jobs with capital letters. So if worker b is assigned to job D, say, it would take that worker 12 time units. There are 24 (=4!) matchings possible for this situation. (Using the Fundamental Principle of Counting one sees that for n workers and n jobs there are n! possible matchings.) A typical one would be a assigned to C, b assigned to A, c assigned to D, and d assigned to C.

What goals might one have for a matching? One might want to:

a. Minimize the sum of the weights of the edges in the matching.

b. Maximize the sum of the weights of the edges in the matching.

c. Minimize the minimum weight of any edge in a matching.

d. Maximize the maximum weight of any edge in a matching.

e. Minimize the maximum weight of any edge in a matching.

f. Maximize the minimum weight of any edge in a matching.

To better understand these 6 different objectives consider the following example:

There are six possible matchings for this problem. Next to each of the matchings is the resulting triple of weights that occurs:

I. aA, bB, cC (9, 31, 16) Min: 9, Max: 31

II. aA, cB, bC (9, 4, 5) Min: 4; Max: 9

III. aB, bA, cC (20, 30, 16) Min: 16; Max: 30

IV. aB, bC, cA (20, 5, 2) Min: 2; Max: 20

V. aC, bB, cA (19, 31, 2) Min: 2; Max: 31

VI. aC, bA, cB (19, 30, 4) Min: 4; Max: 30.

If the goal is:

a. The optimal matching is II

b. The optimal matching is III

c. The optimal matching is either I or V.

d. The optimal matching is either IV or V.

e. The optimal matching is II

f. The optimal matching is III

Exercise:

Can you find a 3x3 example, where by breaking ties if necessary all six of these different criteria lead to a different matching?

An algorithm to solve problems where the objective is a. above is, known as the Hungarian Algorithm and is a polynomial time algorithm. This algorithm can easily be modified to solve problems where the objective is b. as well.