Bicriteria Online Matching: Maximizing Weight and Cardinality

Inspired by online ad allocation problems, many results have been developed for online matching problems. Most of the previous work deals with a single objective, but, in practice, there is a need to optimize multiple objectives. Here, as an illustrative example motivated by display ads allocation, we study a bi-objective online matching problem. 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 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. In this paper, we present both approximation algorithms and hardness results for this problem. An $(\alpha, \beta)$-approximation for this problem is a matching with weight at least $\alpha$ fraction of the maximum weighted matching, and cardinality at least $\beta$ fraction of maximum cardinality matching. We present a parametrized approximation algorithm that allows a smooth tradeoff curve between the two objectives: when the capacities of fixed nodes are large, we give a $p(1- 1/e^{1/p}), (1-p)(1-1/e^{1/1-p})$-approximation for any $0 \le p \le 1$, and prove a `hardness curve' combining several inapproximability results. These upper and lower bounds are always close (with a maximum gap of $9\%$), and exactly coincide at the point $(0.43, 0.43)$. For small capacities, we present a smooth parametrized approximation curve for the problem between $(0,1-1/e)$ and $(1/2,0)$ passing through a $(1/3,0.3698)$-approximation.

• Algorithms and Theory

• Economics and Electronic Commerce