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.
|