Wiki Navigation

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
==== Chapter 1: Introduction: Some Representative Problems ====

===1.1 Stable Matching===

The Stable Matching Problem is based on the question: Could one design a process(college application or job recruiting, for example) that is self-enforcing?  A simplified version of this problem is a situation trying to match n men with n women, taking into account their preferences.  A perfect matching is is a matching in which each man and woman appears in exactly one pairing.  An instability in a matching is when a man and a woman not in a pairing both prefer each other to their current partner.  The goal of the problem is to get a stable matching - one that is perfect and with no instabilities.  The algorithm to achieve this is called the Gale-Shapley algorithm.

A stable matching is one in which individual self-interest will prevent any man/woman from switching pairs.  In analyzing this algorithm, we want to look at a few main propositions.  First, that the G-S algorithm terminates after at most n^2 iterations of the while loop.  Secondly, the set of pairs returned by the algorithm is a stable matching.  Both of these proofs are very well-explained.

The process of designing the algorithm became more clear to me after combining the reading with the lecture.  I sometimes have trouble knowing where to start with a proof or an algorithm design, but the authors explain problems really clearly and then have nice, descriptive proofs.


=== 1.2 Five Representative Problems ===
This section gives a brief introduction to 5 classes of problems and the algorithm classes that can be used to solve them.  It gives an idea of what is to come in the rest of the book.  The five problems are:

1. Interval Scheduling: You have a resource(a lecture room, maybe) and people can request to use it for a time period.  The goal is to maximize the number of request accepted, with no overlap.  A greedy algorithm is appropriate here - it processes the ordered input one piece at a time with no apparent look-ahead.

2. Weighted Interval Scheduling: Each request has a weight or value, and the goal is to maximize the total value.  This would use a dynamic programming technique, which builds up the optimal value over all possible solutions in a compact way that leads to a very efficient solution.

3. Bipartite Matching: A bipartite graph is when the vertices nodes can be split into two sets and all edges have one end in each set.  This problem is an extension of the stable matching problem that models situations when objects are assigned to other objects.  The goal is to find a matching of maximum size.  The algorithm inductively builds up the matchings, and is representative of a class of problems called network flow problems.

4. Independent Set: A subset of a graph is independent if no nodes in the subset are connected.  Thus, the goal is to find the largest independent set, given a graph.  This problem is part of a class of NP-complete problems, which have no known efficient solution.  Currently, the brute-force approach is the best we know.

5. Competitive Facility Location: This is a game-playing problem where players alternate choosing valued locations, wanting the maximum possible value, but they are limited because the set of all chosen locations must be an independent set.  The problem is whether, given a target value, if one player can reach the target, regardless of what other player(s) do.  This problem is in the class of PSPACE-complete problems, which are difficult to solve and prove.

This section was very beneficial to understand the goals of the class and the various algorithms we will learn.  While no real detail is given on any of the problems or algorithms, it is good to get a general idea of the problems we will be facing in this class and be able to start thinking about them.