Theory/Algorithm Talk - Allan Borodin, University of Toronto

Presenter:  Dr. Allan Borodin, Professor, University of Toronto

Host:  David Kirkpatrick

Title:  Revisiting Submodular Function Maximization

Location:  X836 Board Room

Abstract:

Submodular function maximization has generated a substantial amount of recent activity, both in terms of applications as well as new algorithms obtaining improved approximation ratios. There is a nice interplay with algorithmic ideas (i.e. theory) being applied to specific problems and then in turn these problems suggesting some new concepts.

One example of a new abstraction of ideas is the use of ``non oblivious'' local search as applied by Berman to weighted k-set packing and more generally independence in k+1 claw free graphs. This has led to a new class of independence systems called ``k-exchangeable systems''. Within this class of independence systems, non-oblivious local provides improved approximation bounds.
(This is recent work by Justin Ward.)

Another setting is the problem of ranking with diversity where the goal is (for example) to choose a subset S of documents so as to maximize the ``quality'' of the documents in S (say as measured by a submodular function subject to a matroid constraint) while insuring that these documents are diverse in some sense (e.g. maximizing the sum of pairwise ``distances'' between documents). We utilize some ideas about  and local search algorithms to extend previous results for linear quality functions subject to a cardinality (i.e. uniform matroid) constraint. The analysis also suggests a new class of ``weakly submodular functions'' (due to Yuli Ye) which include submodular functions as well as the sum of pairwise distances.
(This is work with Yuli Ye and Hyun Chul Lee).