tailieunhanh - Lecture Algorithm design - Chapter 1: Representative problems
Lecture Algorithm design "Representative problems" include all of the following: Matching med-school students to hospitals, stable matching problem, perfect matching, unstable pair, stable matching problem, stable roommate problem, Gale-Shapley deferred acceptance algorithm,.and another content. | 1. Representative Problems stable matching five representative problems Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley Copyright 2013 Kevin Wayne http wayne kleinberg-tardos Last updated on Mar 14 2014 5 36 PM Section 1. Representative Problems stable matching Matching med-school students to hospitals Goal. Given a set of preferences among hospitals and med-school students design a self-reinforcing admissions process. Unstable pair student x and hospital y are unstable if x prefers y to its assigned hospital. y prefers x to one of its admitted students. Stable assignment. Assignment with no unstable pairs. Natural and desirable condition. Individual self-interest prevents any hospital-student side deal.
đang nạp các trang xem trước