• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 4 fuera de 249 páginas
Examen

Algorithm Design Solutions Manual (2005) by Jon Kleinberg & Éva Tardos | Complete Chapter Solutions | Algorithms Study Guide

Document preview thumbnail
Vista previa 4 fuera de 249 páginas

Algorithm Design Solutions Manual (2005) by Jon Kleinberg & Éva Tardos | Complete Chapter Solutions | Algorithms Study Guide

Vista previa del contenido

1 1

, Stable Matching n




Note: Exercises denoted with an asterisk ( ) tend to be more difficult, or to rely on
n n n n n n n n n n n n n n n n


some of the more advanced material.
n n n n n n




1. Gale and Shapley published their paper on the stable marriage problem in 1962; but a
n n n n n n n n n n n n n n


version of their algorithm had already been in use for ten years by the National Resident
n n n n n n n n n n n n n n n n


Matching Program, for the problem of assigning medical residents to hospitals.
n n n n n n n n n n n



Basically, the situation was the following. There were m hospitals, each with a certain
n n n n n n n n n n n n n


number of available positions for hiring residents. There were n medical students
n n n n n n n n n n n n


graduating in a given year, each interested in joining one of the hospitals. Each hospital
n n n n n n n n n n n n n n n


had a ranking of the students in order of preference, and each student had a
n n n n n n n n n n n n n n n


nranking of the hospitals in order of preference. We will assume that there were more
n n n n n n n n n n n n n n


students graduating than there were slots available in the m hospitals.
n n n n n n n n n n n



The interest, naturally, was in finding a way of assigning each student to at most one
n n n n n n n n n n n n n n n


hospital, in such a way that all available positions in all hospitals were filled.
n n n n n n n n n n n n n n


n(Since we are assuming a surplus of students, there would be some students who do
n n n n n n n n n n n n n n


not get assigned to any hospital.)
n n n n n n



We say that an assignment of students to hospitals is stable if neither of the following
n n n n n n n n n n n n n n n


situations arises.
n n




• First type of instability: There are students s and s , and a hospital h, so that
n n n n n n n n n n n n n n n n



– s is assigned to h, and n n n n n



– sr is assigned to no hospital, and
n n n n n n



– h prefers sr to s. n n n n

r r
Second type of instability: There are students s and s , and hospitals h and h ,
n n n n n n n n n n n n n n n n


so that n



– s is assigned to h, and
n n n n n



– sr is assigned to hr, and
n n n n n



– h prefers sr to s, and
n n n n n



– sr prefers h to hr.
n n n n




So we basically have the stable marriage problem from class, except that (i) hospitals
n n n n n n n n n n n n n


generally want more than one resident, and (ii) there is a surplus of medical
n n n n n n n n n n n n n n


nstudents.
Show that there is always a stable assignment of students to hospitals, and give an
n n n n n n n n n n n n n n


efficient algorithm to find one. The input size is Θ(mn); ideally, you would like
n n n n n n n n n n n n n n


nto find an algorithm with this running time.
n n n n n n n



Solution. The algorithm is very similar to the one from class. At any point in
n n n n n n n n n n n n n n n


ntime, a student is either “committed” to a hospital or “free.” A hospital either has
n n n n n n n n n n n n n n


available positions, or it is “full.” The algorithm is the following:
n n n n n n n n n n n




2

, While some hospital hi has available positions hi offers a position to the next
n n n n n n n n n n n n n


student sj on its preference list if sj is free then sj accepts the offer else
n n n n n n n n n n n n n n n n


(sj is already committed to a hospital hk) if sj prefers hk to hi then sj
n n n n n n n n n n n n n n n n


remains committed to hk else sj becomes committed to hi the number of
n n n n n n n n n n n n n


available positions at hk increases by one. the number of available
n n n n n n n n n n n


positions at hi decreases by one.
n n n n n n




The algorithm terminates in O(mn) steps because each hospital offers a
n n n n n n n n n n


npositions to a student at most once, and in each iteration, some hospital offers a
n n n n n n n n n n n n n n


position to some student.
n n n n



Suppose there are pi > 0 positions available at hospital hi. The algorithm terminates
n n n n n n n n n n n n n


with an assignment in which all available positions are filled, because any hospital that
n n n n n n n n n n n n n n


did not fill all its positions must have offered one to every student; but then, all
n n n n n n n n n n n n n n n n


these students would be committed to some hospital, which contradicts our
n n n n n n n n n n n


nassumption that n

m
i= pi < n.
n
n n

1

Finally, we want to argue that the assignment is stable. For the first kind of
n n n n n n n n n n n n n n


instability, suppose there are students s and sr, and a hospital h as above. If h
n n n n n n n n n n n n n n n n


prefers sr to s, then h would have offered a position to sr before it offered one to s;
n n n n n n n n n n n n n n n n n n n


from then on, sr would have a position at some hospital, and hence would not be
n n n n n n n n n n n n n n n n


free at the end — a contradiction.
n n n n n n n



For the second kind of instability, suppose that (hi, sj) is a pair that causes instability.
n n n n n n n n n n n n n n n


Then hi must have offered a position to sj, for otherwise it has pi residents all of
n n n n n n n n n n n n n n n n n


nwhom it prefers to sj. Moreover, sj must have rejected hi in favor of some hk which
n n n n n n n n n n n n n n n n


he/she preferred; and sj must therefore be committed to some hl (possibly different
n n n n n n n n n n n n n


from hk) which he/she also prefers to hi.
n n n n n n n n




2. We can think about a different generalization of the stable matching problem, in which
n n n n n n n n n n n n n


ncertain man-woman pairs are explicitly forbidden. In the case of employers and ap-
n n n n n n n n n n n n


nplicants, picture that certain applicants simply lack the necessary qualifications or
n n n n n n n n n n


n degree; and so they cannot be employed at certain companies, however desirable they
n n n n n n n n n n n n


nmay seem. Concretely, we have a set M of n men, a set W of n women,
n n n n n n n n n n n n n n n n


nand a set F ⊆ M × W of pairs who are simply not allowed to get married.
n n n n n n n n n n n n n n n n n


n Each man m ranks all the women w for which (m, w) /∈ F , and each woman wr ranks
n n n n n n n n n n n n n n n n n n n


nall the men mr for which (mr, wr) /∈ F .
n n n n n n n n n n



In this more general setting, we say that a matching S is stable if it does not exhibit
n n n n n n n n n n n n n n n n n


nany of the following types of instability.
n n n n n n




(i) There are two pairs (m, w) and (mr, wr) in S with the property that m prefers wr
n n n n n n n n n n n n n n n n n


to w, and wr prefers m to mr. (The usual kind of instability.)
n n n n n n n n n n n n



(ii) There is a pair (m, w) S, and a man mr, so that mr is not part of any pair in the
n n n n n n n n n n n n n n n n n n n n n n


matching, (mr, w) F , and w prefers mr to m. (A single man is more
n n n n n n n n n n n n n n n n


desirable and not forbidden.)
n n n n


3

, (iir) There is a pair (m, w)
n S, and a woman wr, so that wr is not part of
n n n n n n n n n n n n n n n n n n


any pair in the matching, (m, wr) F , and m prefers wr to w. (A single woman
n n n n n n n n n n n n n n n n n n


is more desirable and not forbidden.)
n n n n n n



(iii) There is a man m and a woman w, neither of which is part of any pair in the
n n n n n n n n n n n n n n n n n n


matching, so that (m, w) F . (There are two single people with nothing prevent-
n n n n n n n n n n n n n n n


ing them from getting married to each other.)
n n n n n n n n




Note that under these more general definitions, a stable matching need not be a perfect
n n n n n n n n n n n n n n


matching.
n



Now we can ask: for every set of preference lists and every set of forbidden pairs, is
n n n n n n n n n n n n n n n n


n there always a stable matching? Resolve this question by doing one of the
n n n n n n n n n n n n


nfollowing two things: (a) Giving an algorithm that, for any set of preference lists and
n n n n n n n n n n n n n n


forbidden pairs, produces a stable matching; or (b) Giving an example of a set of
n n n n n n n n n n n n n n n


preference lists and forbidden pairs for which there is no stable matching.
n n n n n n n n n n n n



Solution. There is always a stable matching, even in the general model with forbidden
n n n n n n n n n n n n n


pairs. The most direct way to prove this is through an algorithm that is almost the
n n n n n n n n n n n n n n n n


same as the one we used for the basic stable matching problem in class; indeed, the
n n n n n n n n n n n n n n n n


only change is that our condition for the While loop will say: “While there is a
n n n n n n n n n n n n n n n n


nman m who is free and hasn’t proposed to every woman w for which (m, w) F .”
n n n n n n n n n n n n n n n n n n


nHere is the algorithm in full:
n n n n n




Initially all m ∈ M and w ∈ W are free While there is a man m
n n n n n n n n n n n n n n n n


nwho is free and hasn’t proposed to every woman w for which (m, w)
n n n n n n n n n n n n n


n F Choose such a man m Let w be the highest-ranked woman in
n n n n n n n n n n n n n


nm’s preference list to which m has not yet proposed If w is free
n n n n n n n n n n n n n


nthen (m, w) become engaged Else w is currently engaged to mr If w
n n n n n n n n n n n n n


nprefers mr to m then m remains free Else w prefers m to mr (m, w) become
n n n n n n n n n n n n n n n n


nengaged mr becomes free Endif Endif Endwhile Return the set S of
n n n n n n n n n n n


nengaged pairs n




Now, facts (1.1) - (1.3) from the book remain true; and we don’t have to worry about
n n n n n n n n n n n n n n n n


establishing that the resulting matching S is perfect (indeed, it may not be). We also
n n n n n n n n n n n n n n n


notice an additional pairs of facts. If m is a man who is not part of a pair in S,
n n n n n n n n n n n n n n n n n n n n


then m must have proposed to every non-forbidden woman; and if w is a woman who
n n n n n n n n n n n n n n n n


is not part of a pair in S, then it must be that no man ever proposed to w.
n n n n n n n n n n n n n n n n n n n



Finally, we need only show n n n n




• There is no instability with respect to the returned matching S.
n n n n n n n n n n




Our general definition of instability has four parts; this means that we have to
n n n n n n n n n n n n n


nmake sure none of the four bad things happens.
n n n n n n n n



First, suppose that there is an instability of type (i), consisting of pairs (m, w)
n n n n n n n n n n n n n n


nand (mr, wr) in S with the property that m prefers wr to w, and wr prefers m to mr.
n n n n n n n n n n n n n n n n n n n


nIt follows that m must have proposed to wr; so wr rejected m, and thus she
n n n n n n n n n n n n n n n



4

Información del documento

Subido en
17 de octubre de 2026
Número de páginas
249
Escrito en
2026/2027
Tipo
Examen
Contiene
Preguntas y respuestas
$17.99

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
Clonesmtb
3.3
(8)
Vendido
36
Seguidores
0
Artículos
258
Última venta
1 mes hace



Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes