Yossi Azar
Ranking with Unrelated Intents or Submodular Valuations
ABSTRACT:
Consider the following web-search ranking problem.
There is a set of m search result pages (items) and there are n
user types of known proportion. Each user type has a relevance
function that quantifies the information that it gains from
inspecting any subset of items. The goal is to order the items
in a way that minimizes the average effort of the user types.
The effort of a user type is the number of items it has to
review until it gains a critical mass of relevant information.
When the relevance function for each type is a linear function
over the items then the problem is called "Ranking with
Unrelated Intents" (note - the function is different for each
type). A more general case is when the relevance function for
each type is submodular (modeling overlaps between the
information gained from the items). We call it "Ranking with
Submodular Valuations". We show a constant approximation
algorithm for Ranking with Unrelated Intents and a logarithmic
approximation for Ranking with Submodular Valuations.
Joint work with my student Iftah Gamzu.
BIO:
Yossi Azar is a Professor of Computer Science in Tel-Aviv
university. He received his Ph.D. from Tel-Aviv University in
1989. He spent several years in Stanford, DEC and IBM and
joined Tel-Aviv university in 1994. Between 2002-2004 Yossi was
the chair of the department of Computer Science in Tel-Aviv
university. From 2006 until 2009 he was on extended sabbatical
in Microsoft Research, Redmond as visiting principal
researcher. His research interests include mainly design and
analysis of combinatorial optimization algorithms. In
particular problems related to resource allocation as well as
algorithmic game theory.