Optimality in Matching Problems

Ran Duan & Chien-Chung Huang

Optimality in Matching Problems

Matching is a fundamental concept in computer science. Besides having numerous applications, its study has led to many important advances in polyhedral combinatorics, graph theory, and algorithm design.

In a matching problem, we are given a graph with a set of vertices and edges. We want a matching, which is a subset of the given edges where none of these edges share an endpoint. Moreover, the matching should satisfy certain optimality criteria (often depending on the applications). We discuss a few com- mon optimality criteria and our obtained results below.

Matching under preferences: stability and popularity

Suppose that a set of boys and girls are given, each with a preference over the members of the other sex. Ideally, we would like to have a “good” matching – a matching in which the boys and girls would be happy with the current situation. One possible optimality condition to capture the “goodness” of a matching is that of the stability: a matching is stable if no two persons strictly prefer each other to their assigned girlfriend/boyfriend. How to fi nd a stable matching in this context is often called the stable marriage problem. This problem has many important applications in real world, the most famous one being the NRMP program in the United States, where the medical residents are assigned to the hospitals.

Another possible optimality condition is that of the popularity. A matching is more popular than another if more people prefer the former to the latter. A matching is popular if there is no matching more popular than it. Roughly speaking, popularity can be regarded as a sort of “global” stability: that is, we want a situation in which the majority of the people prefer the matching.

We remark that both popular matchings and stable matchings are very active research topics. Every year many research papers are published discussing various aspects of them. In particular, just recently, Alvin Roth and Lloyd Shapley have been awarded the Nobel prize in economics for their work on stable matching and market design.

We show that fi nding a popular matching of the maximum size can be done in polynomial time and a generalization of the stable matching problem, called classifi ed stable matching, can be solved in polynomial time as well.

Maximum weight matching: approximate approach

In the maximum weight matching problem, we want the sum of weights of edges in the matching to be maximum. The most traditional and important motivation of maximum/minimum weight matching is the assignment problem, one of the fundamental combinatorial optimization problems. In this problem, there are a number of workers and the same number of tasks. Any worker can be assigned to perform some task, with different costs/benefi ts. It is required to perform all tasks by assigning exactly one worker to each task in such a way that the total cost of the assignment is minimized or the total benefit is maximized.

If we represent every worker and task by a vertex in the graph, and the weight of the edge between a worker and a task is the cost/benefit of assigning the worker to the task, it is easy to see that the assignment problem is equivalent to the minimum/maximum weight matching problem. Note that such a graph is bipartite, but there are also motivations to fi nd maximum matchings in general graphs, which will greatly complicate the algorithm.

Although the maximum weight matching problem has been studied for decades, the computational complexity of finding an optimal matching remains quite open. We gave the first linear-time algorithm for computing the approximate maximum matching in general graphs, which can achieve an arbitrarily small approximation ratio.