Google Research

Biobjective Online Bipartite Matching

Workshop in Internet and Network Economics, Springer (2014), pp. 218-231

Abstract

Motivated by Online Ad allocation when there are multiple conflicting objectives, we introduce and study the problem of Biobjective Online Bipartite Matching, a strict generalization of the standard setting of Karp, Vazirani and Vazirani, where we are allowed to have edges of two colors, and the goal is to find a matching that is both large and balanced at the same time. We study both deterministic and randomized algorithms for this problem; after showing that the single color upper bounds of 1/2 and 1 − 1/e carry over to our biobjective setting as well, we show that a very natural, albeit hard to analyze, deterministic algorithm achieves a competitive ratio of 0.343. We next show how a natural randomized algorithm matches this ratio, through a simpler analysis, and how a clever – and perhaps not immediately obvious – generalization of Ranking can beat the 1/2 bound and get a competitive ratio of 0.573, coming close to matching the upper bound of 0.63.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work