2.00 p.m.
Greedy Matchings
Kavitha Telikepalli
TIFR, Mumbai.
27-09-12

---

Abstract

Given a bipartite graph G and a family of edge weight functions w_1,...,w_r, we consider the problem of computing a matching M in G that has the maximum weight with respect to w_1, subject to this, has maximum weight with respect to w_2, and so on. This problem is an abstraction of several known variants of matching problems with preferences like rank-maximal matchings and fair matchings. This problem can be solved by reducing all the r weight functions into a single weight function. We show a simple iterative algorithm for this problem that is more efficient.