Rank-Maximal Matchings

• cours magistral - matière potentielle : notes
• exposé

Rank-Maximal Matchings Robert W. Irving Telikepalli Kavitha† Kurt Mehlhorn† Dimitrios Michail‡ Katarzyna Paluch§ Abstract Suppose that each member of a setA of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and sub- ject to that condition, the maximum possible number are matched to their second choice post, and so on.

• largest rank that an applicant uses
• maximal matching
• maximum matching
• rank
• 2 edges
• edges
• edge
• algorithm
• applicant
• graph
• problem