算法设计课后答案Jon Kleinberg(英文)

This is true. Indeed, consider such a pair(rm, a) and consider a perfectrnatching CoIl- t aining pairs(m, wu) and(m!, m ), and, hence, not(m, u). Then since m, and w each rank thc othcr first, they cach prcfcr the other to thcir partners in this matching, and so this matching cannot be stable ex742.158311 There is not always a stable pair of schedules. Suppose Network A has two shows (1, a21 with ratings 20 and 40; and Network d has two shows id1, d) with ratings 10 and 30 Each nctwork can rovcal onc of two schedules. If in the resulting pair, an is paired against d1, then Network D will want to switch the order of the shows in its schedule(so that it will win one slot rat. her than none). If in the resulting pair, a1 is paired against d2, then Network A will want to switch the order of the shows in its schedule(so that it will win two slots rather than one eX468.481.560 The algorithIn is very sinilar to the basic Gale-Shapley algorithn from the text. At any point in time, a student is either“ committed” to a hospital or"“free:” hospital either has availablc positions, or it is"full. Thc algorithm is thc following While some hospital hi has available positions hi offers a position to the next student s; on its preference list if s, is free then Bj accepts the offer else (si is already committed to a hospital hk:) if s, prefers hk to hu,then S; remains committed to hk else s, becomes committed to h the number of available positions at hlk increases by one the number of available positions at hi decreases by one Thc algorithm terminates in O(mn stcps bccausc cach hospital offcrs a positions to a student at most once, and in cach iteration, somc hospital offcrs a position to some student Suppose there are pi >o 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 woulld be committed to some hospital, which contradicts our assumption that 2 pi< n Finally, we want to argue that the assignment is stable. For the first kind of instability suppose there are students s and s, and a hospital h as above. Ifh prefers s to s, then h woIld have offered a position to s before it, offered one to s from then on, s 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, Si)is a pair that causes instability Then hi must have offered a position to si, for ot, herwise it has pi residents all of whom it. prefers to si. Moreover, s, must have rejected h: in favor of some h Which he/ she preferred and S, must therefore be committed to some he(possibly different from hk)which he/she also prefers to h ex304.339.892 (a) The answer is Yes. A siInple way to think about it is to break the ties in soine fashion and then run the stable mat ching algorithm on the resulting preference lists. We can for cxamplc brcak the tics lexicographically that is if a man m is indifferent bctwccn two women wi and w; then wi appears on ms preference list before wi if 2 g and if 0