SOLUTION MANUAL
All Chapters Included
1
, ALGORITHM DESIGN SOLUTIONS MANUAL BY JON
KLEINBERG EVA TARDOS
1 Stable Matching
∗ ( ) tend to be more difficult, or to rely
Note: Exercises denoted with an asterisk
on some of the more advanced material.
1. Gale and Shapley published their paper on the stable marriage problem in
1962; but a version of their algorithm had already been in use for ten years
by the National Resident Matching Program, for the problem of assigning
medical residents to hospitals.
Basically, the situation was the following. There were m hospitals, each with
a certain number of available positions for hiring residents. There were n
medical students graduating in a given year, each interested in joining one of
the hospitals. Each hospital had a ranking of the students in order of
preference, and each student had a ranking of the hospitals in order of
preference. We will assume that there were more students graduating than
there were slots available in the m hospitals.
The interest, naturally, was in finding a way of assigning each student to at
most one hospital, in such a way that all available positions in all
hospitals were filled. (Since we are assuming a surplus of students, there
would be some students who do not get assigned to any hospital.)
We say that an assignment of students to hospitals is stable if neither of the
following situations arises.
• First type of instability: There are students sr and s , and a hospital h, so that
– s is assigned to h, and
– sr is assigned to no hospital, and
– h prefers sr to s.
r r
• Second type of instability: There are students s and s , and hospitals h and
h,
so that
– s is assigned to h, and
– sr is assigned to hr, and
– h prefers sr to s, and
– sr prefers h to hr.
So we basically have the stable marriage problem from class, except that (i)
hospitals generally want more than one resident, and (ii) there is a surplus
of medical students.
2
,Show that there is always a stable assignment of students to hospitals, and
give an efficient algorithm to find one. The input size is Θ(mn); ideally,
you would like to find an algorithm with this running time.
Solution. The algorithm is very similar to the one from class. At any
point in time, a student is either “committed” to a hospital or “free.” A
hospital either has available positions, or it is “full.” The algorithm is the
following:
While some hospital hi has available positions hi offers a position
to the next student sj on its preference list if sj is free then sj
accepts the offer else (sj is already committed to a hospital hk) if
sj prefers hk to hi then sj remains committed to hk else sj
becomes committed to hi the number of available positions at hk
increases by one. the number of available positions at hi
decreases by one.
The algorithm terminates in O(mn) steps because each hospital offers a
positions to a student at most once, and in each iteration, some hospital
offers a position to some student.
Suppose there are pi > 0 positions available at hospital hi. The algorithm
terminates with an assignment in which all available positions are filled,
because any hospital that did not fill all its positions must have offered
one to every student; but then, all these students would be committed to
Σ
some hospital, which contradicts our assumption that
m
i= pi < n.
1
3
, Finally, we want to argue that the assignment is stable. For the first kind
of instability, suppose there are students s and sr, and a hospital h as
above. If h prefers sr to s, then h would have offered a position to sr
before it offered one to s; from then on, sr would have a position at some
hospital, and hence would not be free at the end — a contradiction.
For the second kind of instability, suppose that (hi, sj) is a pair that
causes instability. Then hi must have offered a position to sj, for otherwise
it has pi residents all of whom it prefers to sj. Moreover, sj must have
rejected hi in favor of some hk which he/she preferred; and sj must
therefore be committed to some hl (possibly different from hk) which he/she
also prefers to hi.
2. We can think about a different generalization of the stable matching problem,
in which certain man-woman pairs are explicitly forbidden. In the case of
employers and ap- plicants, picture that certain applicants simply lack the
necessary qualifications or degree; and so they cannot be employed at
certain companies, however desirable they may seem. Concretely, we have
a set M of n men, a set W of n women, and a set F ⊆ M × W of pairs
who are simply not allowed to get married. Each man m ranks all the
women w for which (m, w) /∈ F , and each woman wr ranks all the men mr
for which (mr, wr) /∈ F .
In this more general setting, we say that a matching S is stable if it does
not exhibit any of the following types of instability.
(i) There are two pairs (m, w) and (mr, wr) in S with the property that m prefers
wr
to w, and wr prefers m to mr. (The usual kind of instability.)
(ii) There is a pair (m,∈ w) S, and a man mr, so that mr is not part of
any pair in the/∈matching, (mr, w) F , and w prefers mr to m. (A
single man is more desirable and not forbidden.)
(ii ) There is a pair (m,∈w)
r
S, and a woman wr, so that wr is not part
/∈
of any pair in the matching, (m, wr) F , and m prefers wr to w. (A
single woman is more desirable and not forbidden.)
(iii) There is a man m and a woman w, neither of which is part of any
pair in the matching,/∈so that (m, w) F . (There are two single people
with nothing prevent- ing them from getting married to each other.)
Note that under these more general definitions, a stable matching need not
be a perfect matching.
Now we can ask: for every set of preference lists and every set of forbidden
pairs, is there always a stable matching? Resolve this question by doing
one of the following two things: (a) Giving an algorithm that, for any set of
4
All Chapters Included
1
, ALGORITHM DESIGN SOLUTIONS MANUAL BY JON
KLEINBERG EVA TARDOS
1 Stable Matching
∗ ( ) tend to be more difficult, or to rely
Note: Exercises denoted with an asterisk
on some of the more advanced material.
1. Gale and Shapley published their paper on the stable marriage problem in
1962; but a version of their algorithm had already been in use for ten years
by the National Resident Matching Program, for the problem of assigning
medical residents to hospitals.
Basically, the situation was the following. There were m hospitals, each with
a certain number of available positions for hiring residents. There were n
medical students graduating in a given year, each interested in joining one of
the hospitals. Each hospital had a ranking of the students in order of
preference, and each student had a ranking of the hospitals in order of
preference. We will assume that there were more students graduating than
there were slots available in the m hospitals.
The interest, naturally, was in finding a way of assigning each student to at
most one hospital, in such a way that all available positions in all
hospitals were filled. (Since we are assuming a surplus of students, there
would be some students who do not get assigned to any hospital.)
We say that an assignment of students to hospitals is stable if neither of the
following situations arises.
• First type of instability: There are students sr and s , and a hospital h, so that
– s is assigned to h, and
– sr is assigned to no hospital, and
– h prefers sr to s.
r r
• Second type of instability: There are students s and s , and hospitals h and
h,
so that
– s is assigned to h, and
– sr is assigned to hr, and
– h prefers sr to s, and
– sr prefers h to hr.
So we basically have the stable marriage problem from class, except that (i)
hospitals generally want more than one resident, and (ii) there is a surplus
of medical students.
2
,Show that there is always a stable assignment of students to hospitals, and
give an efficient algorithm to find one. The input size is Θ(mn); ideally,
you would like to find an algorithm with this running time.
Solution. The algorithm is very similar to the one from class. At any
point in time, a student is either “committed” to a hospital or “free.” A
hospital either has available positions, or it is “full.” The algorithm is the
following:
While some hospital hi has available positions hi offers a position
to the next student sj on its preference list if sj is free then sj
accepts the offer else (sj is already committed to a hospital hk) if
sj prefers hk to hi then sj remains committed to hk else sj
becomes committed to hi the number of available positions at hk
increases by one. the number of available positions at hi
decreases by one.
The algorithm terminates in O(mn) steps because each hospital offers a
positions to a student at most once, and in each iteration, some hospital
offers a position to some student.
Suppose there are pi > 0 positions available at hospital hi. The algorithm
terminates with an assignment in which all available positions are filled,
because any hospital that did not fill all its positions must have offered
one to every student; but then, all these students would be committed to
Σ
some hospital, which contradicts our assumption that
m
i= pi < n.
1
3
, Finally, we want to argue that the assignment is stable. For the first kind
of instability, suppose there are students s and sr, and a hospital h as
above. If h prefers sr to s, then h would have offered a position to sr
before it offered one to s; from then on, sr would have a position at some
hospital, and hence would not be free at the end — a contradiction.
For the second kind of instability, suppose that (hi, sj) is a pair that
causes instability. Then hi must have offered a position to sj, for otherwise
it has pi residents all of whom it prefers to sj. Moreover, sj must have
rejected hi in favor of some hk which he/she preferred; and sj must
therefore be committed to some hl (possibly different from hk) which he/she
also prefers to hi.
2. We can think about a different generalization of the stable matching problem,
in which certain man-woman pairs are explicitly forbidden. In the case of
employers and ap- plicants, picture that certain applicants simply lack the
necessary qualifications or degree; and so they cannot be employed at
certain companies, however desirable they may seem. Concretely, we have
a set M of n men, a set W of n women, and a set F ⊆ M × W of pairs
who are simply not allowed to get married. Each man m ranks all the
women w for which (m, w) /∈ F , and each woman wr ranks all the men mr
for which (mr, wr) /∈ F .
In this more general setting, we say that a matching S is stable if it does
not exhibit any of the following types of instability.
(i) There are two pairs (m, w) and (mr, wr) in S with the property that m prefers
wr
to w, and wr prefers m to mr. (The usual kind of instability.)
(ii) There is a pair (m,∈ w) S, and a man mr, so that mr is not part of
any pair in the/∈matching, (mr, w) F , and w prefers mr to m. (A
single man is more desirable and not forbidden.)
(ii ) There is a pair (m,∈w)
r
S, and a woman wr, so that wr is not part
/∈
of any pair in the matching, (m, wr) F , and m prefers wr to w. (A
single woman is more desirable and not forbidden.)
(iii) There is a man m and a woman w, neither of which is part of any
pair in the matching,/∈so that (m, w) F . (There are two single people
with nothing prevent- ing them from getting married to each other.)
Note that under these more general definitions, a stable matching need not
be a perfect matching.
Now we can ask: for every set of preference lists and every set of forbidden
pairs, is there always a stable matching? Resolve this question by doing
one of the following two things: (a) Giving an algorithm that, for any set of
4
