Chennai Mathematical Institute

Seminars




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.