**PGCSE104: Advanced Algorithms
Module VI - (4L)
Matching Problems**
In this module, we will explore matching problems, particularly the Stable Marriage
Problem, Hospital-Resident Problem, and Amortized Analysis. Each of these problems involves
pairing or allocating resources efficiently and fairly.
1. Stable Marriage Problem
The Stable Marriage Problem is a classic matching problem where we aim to find a stable
matching between two equally sized sets (typically referred to as men and women) such that no
pair of individuals prefers each other over their current partners.
Problem Statement
Given two sets of individuals (men and women), each individual ranks all members of the opposite
set in order of preference. The goal is to find a stable matching such that no man and woman
prefer each other over their assigned partners.
Gale-Shapley Algorithm (Deferred Acceptance)
The Gale-Shapley algorithm solves the Stable Marriage Problem by iteratively pairing men and
women based on their preferences:
1. Initially, all men are unengaged, and each woman is free.
2. Each unengaged man proposes to his most-preferred woman who hasn't yet rejected him.
3. Each woman evaluates the proposals she receives. She either:
Stays with her current partner if he is preferable, or
Engages with a new man and rejects her current partner (if the new one is preferable).
4. This process continues until all men and women are paired.
The result is a stable matching, where no man-woman pair would prefer to leave their current
partners for each other.
Code Example (Python)
python Copy code
def stable_marriage(men_preferences, women_preferences): n = len(men_preferences)
free_men = list(range(n)) engaged = [-1] * n women_engaged = [-1] * n
men_next_proposal = [0] * n while free_men: man = free_men.pop(0) woman =
men_preferences[man][men_next_proposal[man]] men_next_proposal[man] += 1 if
women_engaged[woman] == -1: # Woman is free women_engaged[woman] = man engaged[man] =
woman else: current_partner = women_engaged[woman] if
women_preferences[woman].index(man) <
women_preferences[woman].index(current_partner): # Woman prefers new man
free_men.append(current_partner) women_engaged[woman] = man engaged[man] = woman
else: # Woman stays with current partner free_men.append(man) return engaged #
Example usage men_preferences = [[0, 1, 2], [2, 0, 1], [1, 0, 2]] women_preferences =
[[0, 1, 2], [1, 2, 0], [2, 1, 0]] print("Stable pairs:",
stable_marriage(men_preferences, women_preferences))
Time Complexity
The time complexity of the Gale-Shapley algorithm is O(n2 ), where n is the number of men or
women.
2. Hospital-Resident Problem
The Hospital-Resident Problem is a generalization of the Stable Marriage Problem, where
hospitals (with multiple available positions) must be matched with residents (who prefer certain
hospitals). The goal is to find a stable matching where no resident and hospital pair would rather
be assigned to each other than their current assignments.
Problem Statement
Each hospital can accept multiple residents, and each resident prefers certain hospitals.
Each hospital ranks its resident applicants.
The goal is to find a stable matching where no resident-hospital pair would prefer to be
matched with each other over their current assignment.
Solution Using Gale-Shapley Algorithm
The Hospital-Resident Problem can be solved using a modified version of the Gale-Shapley
algorithm. The main difference is that hospitals now have capacities (the number of residents they
can accept).
Algorithm
1. Residents propose to hospitals based on their preferences.
2. Hospitals tentatively accept residents up to their capacity and reject the least preferred ones.
3. Rejected residents continue proposing to their next preferred hospital.
4. This process continues until no resident can propose further.
3. Amortized Analysis
Amortized Analysis is a technique used in algorithm analysis to determine the average time per
operation over a sequence of operations, rather than the worst-case time for a single operation.
This is useful in understanding the efficiency of algorithms that might have occasional expensive
operations but perform efficiently over time.
Three Methods of Amortized Analysis:
1. Aggregate Analysis:
Calculate the total cost of n operations and then divide by n to get the average cost per
operation.
Example: Consider a dynamic array where resizing happens when it is full. Over time,
even though resizing is expensive, most insertions are constant time, and the overall
average time per insertion is O(1).
2. Accounting Method:
Assign an artificial "charge" to each operation, ensuring that expensive operations are
paid for in advance by cheaper operations.
Example: When inserting into a dynamic array, each insertion might have a "charge" to
pay for future resizing.
3. Potential Method:
Define a potential function that reflects the state of the data structure. The amortized
cost of an operation is the actual cost plus the change in potential.
Example: In a dynamic array, the potential might reflect how full the array is, with the
potential increasing as the array nears capacity.
Example: Amortized Analysis for Dynamic Arrays
Consider a dynamic array that doubles in size when full:
On most insertions, the cost is O(1).
When resizing occurs, it costs O(n) to copy all elements to a new array.
Over n operations, the total cost of resizing is O(n), and the amortized cost per insertion is
O(1).
Summary
In this module, we examined key matching problems and amortized analysis:
Stable Marriage Problem: The Gale-Shapley algorithm provides a stable matching between
two sets.
Hospital-Resident Problem: A generalization of the Stable Marriage Problem where hospitals
can accept multiple residents.
Amortized Analysis: A technique to analyze the average time complexity of an algorithm over
a sequence of operations, offering a better understanding of performance over time.
Each of these problems is fundamental in optimization and allocation, with applications in real-
world scenarios like matching markets and resource management.