The Stable Matching Problem

Proof by Contradiction

• Definition
• applications
• connection to matching multiple others
• Idea of blocking pairs: A pair $(m, w)$ is called a blocking pair for a marriage matching, M, if both m and w prefer each other more than there mate in the marriage, M. M is stable if there is no blocking pair.
• Gale/Shapley algorithm and its analysis.

Greedy Algorithms

Proof by induction: Prove that if nothing got messed up in the first $(t-1)$ steps, the t-th step doesn't mess up either

Start with some (unknown) optimal solution O, and we prove that gradually making it more similar to our (greedy) solution can only make it better (or equal).

Figure out as much as possible about what the optimum solution must look like (properties like what must be included, what cannot be included). This often suggests a natural algorithm.

• Basic Ideas: Algorithm that makes irrevocable local choices, usually based on a fairly simple rule.
• "Greedy Stays Ahead": This style of proof works by showing that, according to some measure, the greedy algorithm always is at least as far ahead as the optimal solution during each iteration of the algorithm
• Exchange Arguments: They work by showing that you can iteratively transform any optimal solution into the solution produced by the greedy algorithm without changing the cost of the optimal solution, thereby proving that the greedy solution is optimal.
• Specific Algorithms
• Cut property: $S\subseteq V, S\neq \emptyset, S\neq V, \overline {S}\coloneqq V\backslash S$ ( exchange argument)

Divide & Conquer

Induction on input size: the correctness of the whole algorithm requires that the recursive calls gave the correct answers

• Basic Ideas: Take a problem (of size n). Produce from it one or more subproblems of size smaller than n. Solve these subproblems independently (recursively). Aggregate their solutions into a solution for the original problem
• Whenever you have a Divide&Conquer Algorithm, the correctness proof almost always uses induction on the input size. The reason is that the correctness of the whole algorithm requires that the recursive calls gave the correct answers.