Chapter 1

This chapter consists of 6 different problems, namely Stable Matching, Interval Scheduling, Weighted Interval Scheduling, Bipartite Matching, Independent Set and Competitive Facility Location. There is a detailed explanation about Stable Matching, with its history, examples, design of its algorithm, its analysis, extensions and proofs. For the rest, the chapter provides information on how these problems are to be dealt with.

David Gale and Lloyd Shapley, two mathematical economists designed the Stable Matching Problem in 1962, to design a self-enforcing matching algorithm to match elements of Set X with elements of Set Y depending on their preferences and limits. The book gives an example of one such Stable Matching Problem: a set of men to be matched with a set of equal number of women to get married to.

• Set all Men(M) and Women(W) to be free
• While there exists a Man who is free and hasn't proposed all Women
  • Choose such a man, m
  • Let w be the highest preferred woman in m's list of preferred women to whom m hasn't proposed yet
  • If w is free
    • m and w are engaged
  • Else if w is engaged to m'
    • If w prefers m' to m
      • m is still free
    • Else if w prefers m to m'
      • m and w are engaged
      • m' becomes free
    • End if
  • End if
• Return the set of paired m and w

• w gets engaged from the moment she receives a proposal and her partner only keeps getting better, but not worse in terms of her preference
• It is reversed for m, i.e. his partner keeps getting worse in terms of his preference
• Since at most, each m proposes each w only once, the algorithm has an upper bound order of n^2
• If m is free at any point, then there should be a w to whom he hasn't proposed yet. This is because there are the same number of w as m
• The set returned at the end is a perfect matching
• Every execution returns the same set (Need help)
• In Stable Matching S*, each w is paired with her worst valid m (Need help)

The goal of this problem is to maximize the number of requests for a resource which can be used by a single person at a time. For this, we say a set of requests are compatible if no two requested intervals do not overlap. Out of all these compatible sets, we choose the one with the maximum size. This is an example of “Greedy Algorithm”.

This is almost the same as Interval Scheduling, except that each task has a weight, or a value assigned to it. For example, if task 1 has a higher weight over all other tasks, task 1 has to be included in the optimal solution. For this, we use a technique called “Dynamic Programming”.

In the Stable Matching problem, if any m does not want to marry at least one of w, Bipartite Matching problem occurs. This problem can be solved by a method known as “Augmentation”. An example of this is “Network Flow Problems”.

It is a more general way of defining a Stable Matching or a Bipartite Matching problems. For example, this problem helps you solve your problem of inviting a group of friends for a party such that there is no tension between any of them in the party because of any one of them not getting along with any of the rest. This problem has no known efficient algorithm and the only way to solve this problem is by brute force and trying out each subsets. This is an example of an “NP-complete” problem.

This problem is like a game played by two franchises trying to maximize their output by selecting different locations available, turn by turn, with rules that each of them cannot be too close to each other. This is an example of “PSPACE-complete problems”, which is believed to be strictly harder than “NP-complete problems”.

Definitely did give me an idea of what we would be dealing in this class. Sounds fun. Though I have a question, why would there be the same pairs in each execution of the Stable Matching Algorithm on a set of data?

Aside from that, I thought the chapter was smooth and was understandable. Class discussions helped too.