Fei Chen: Oblivious and online matching via continuous linear programming

Practicalities

Lunch is served at 12:00 noon (register at  this doodle  at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

ABSTRACT

Variants of the maximum matching problem have wide applications in the real world. Motivated by a kidney exchange program, where kidney transfer is expected to be performed right after patients and donors pass the compatibility tests, the oblivious matching problem was proposed allowing greedy matching algorithms only. Motivated by online advertising, where for each keyword arriving online the advertising system should immediately decide which ad to display to maximize the profit, the online matching setting was proposed that requires the algorithm to maintain a matching in an online fashion.

We study the oblivious and online matching problems. For oblivious matching, we prove that the Ranking algorithm has a performance ratio of at least 0.523 on arbitrary graphs. For edge-weighted online bipartite b-matching, we give a procedure to construct an asymptotically optimal algorithm. The analysis of both problems relies on linear programming framework. We use a continuous linear programming approach to analyze the limiting behavior of normal LPs. In particular, our results for online bipartite b-matching are based on a generalized secretary problem. The continuous LP gives a clear perspective on the secretary problem from which we are able to make a connection between secretary and online matching.