Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
== 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
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
