Chapter 1: Introduction

The problem of stable matching is best explained using an example. In class we used bachelors and bachelorettes. Suppose some man m is engaged to some woman w, and another man m' is engaged to another woman w'. Now, suppose that m prefers w' to w, and w' prefers to m to m'. It would be preferable for m and w' to break their engagements, since each would be happier together than they are currently. This is an unstable situation. A solution to this problem would be a set of engagements in which no unstable pairings exist. If each person's preference list for the opposite sex is provided, is it possible to construct such a set?

1. Interval scheduling
2. Weighted interval scheduling
3. Bipartite matching
4. Independent set
5. Competitive facility location

And then ITS decreed, “Computer labs shall remain locked at all times and under any circumstances, except when a university professor schedules hours in them in advance.” Professor Sprenkle has to register lab times with Steve now. She tells Steve, “I want to use the computer lab on M,W,F from 10:10 am to 11:05 am.” Then Professor Stough enters, asking if he can reserve the room for F, 10:45 to 12:45 to teach a C++ workshop to his CS340 students. How does Steve determine who gets to reserve the room on F morning (there is an overlap from 10:45 to 11:05)? The time overlap of these “requests” makes the requests incompatible, and so one of the requests must be rejected. We want “to select a compatible subset of requests of maximum possible size.”

This is similar to the interval scheduling problem; the difference is that each request has an associated value (weight). We no longer want to accept the maximum number of compatible requests. We want to accept the subset of requests that yields the maximum sum value.

Bipartite graphs can model assignments (likes jobs being assigned to machines). Each job should be matched to a machine, and each machine should be matched to a job. We represent bipartite graphs as two columns of nodes, with edges (assignments) from nodes in the first column to nodes in the second column. The stable matching problem is an example of bipartite matching. More formally, such a problem is defined in the following way: “Given an arbitrary bipartite graph G, find a matching of maximum size. If |X| = |Y| = n, then there is a perfect matching if and only if the maximum matching has size n.”

A set of nodes is independent if no two nodes in S are joined by an edge. Example problem: you have n friends, some pairs don't get along. Find the maximum number of friends you can invite to say a birthday party and avoid any conflicts. Interval scheduling and bipartite matching can both be thought of (encoded) as special cases of the independent set problem. There is no efficient algorithm for the independent set problem currently. We will see later that “Independent Set” is one problem in the large class of NP-complete problems.

Walmart vs K-Mart. Both companies want to build stores in convenient locations (to increase market share, etc.). But all around the country, local zoning regulations prevent the franchises from being located too near one another. Assume the geographic region over which they are vying for control is divided into n zones (1, 2, …, n), and each zone has an associated value (the expected revenue for each company if it opens a store there). Who will win the game? Which company will open a store in location X, Y, Z?