講演者: Amy Langville 氏 (College of Charleston)
タイトル:
The Science of Ranking Items: from webpages to sports teams to movies
概要:
There are many applications that rely heavily on ranked lists. For
instance, search engines present a ranked list of results to users.
Voters rank political candidates in an election. Companies like Netflix
produce lists of the highest ranked movies. Algorithms from numerical
linear algebra and optimization are typically used to create these ranked
lists. I will discuss several popular methods and present a few new
ranking methods. Because different algorithms produce different
ranked lists, one aim is to merge the results from several ranked lists
(or rating lists) into one aggregated list that contains the best qualities
from the various input lists. I will discuss a few algorithms for rank
aggregation and conclude with some applications.
講演者: 岩田 覚 氏 (京都大学 数理解析研究所)
タイトル:
Approximating Submodular Functions Everywhere
概要:
Submodular functions are discrete analogues of convex functions.
Examples include cut capacity functions, matroid rank functions,
and entropy functions. Algorithms that involve submodular functions
usually assume that they are given by an evaluation oracle.
In particular, submodular functions can be minimized by using only
polynomially many queries to the oracle.
In this talk, we consider the problem of approximating a nonnegative,
monotone, submodular function everywhere, after only polynomial number
of oracle queries. The result is based on approximately finding
a maximum volume inscribed ellipsoid in a symmetrized polymatroid.
The analysis uses the greedy algorithm for approximately maximizing
a monotone submodular function subject to a cardinality constraint
by Nemhauser, Wolsey, and Fischer (1978).
This is joint work with Michel Goemans, Nick Harvey, and Vahab Mirrokni.