CATS-Oct-12-2012
Title
Bicriteria Online Matching: Maximizing Weight and Cardinality
Speaker
Nitish Korula, Research Scientist at Google
Abstract
Inspired by online ad allocation problems and applicability of various combinatorial techniques, many new results have been developed for online matching problems during the past decade. Most of the previous work deals with single objective functions, but there is a need to optimize multiple objective functions in advertising applications. In this talk, as an illustrative example motivated by display advertising problems, I will focus on simultaneously maximizing two objectives: the cardinality and the total weight of the matching.
In particular, we consider a set of fixed nodes (ads) with capacity constraints, and a set of online items (pageviews) arriving one by one. Upon arrival of an online item i, a set of eligible fixed neighbors (ads) for the item is revealed, together with a weight w_ia for each eligible neighbor a. The problem is to assign each item to an eligible neighbor online, while respecting the capacity constraints; the goal is to maximize both the total weight of the matching and the cardinality (i.e. the total number of assigned items).
We obtain both approximation algorithms and hardness results for this problem: An (α,β)-approximation for this problem is a matching with weight at least α fraction of the best weight of the maximum weighted matching, and cardinality at least β fraction of the cardinality of maximum matching. I will discuss parametrized algorithms that permit smooth tradeoff curves between the objectives, and briefly touch upon inapproximability results which combine to yield a 'hardness curve' for the problem; these upper and lower bounds are always close, and coincide in tangents at 3 points.
Joint work with Vahab Mirrokni and Morteza Zadimoghaddam