第14回研究会(2009年1月31日(土) 14時〜)講演概要

会場: 秋葉原ダイビル 12階 公立大学法人首都大学東京 秋葉原サテライトキャンパス  詳細はこちら

講演者: 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.

ホーム

Copyright, S@CO All rights reserved, 2006-2009.