Date: Jan. 6 (Tue), 2015
Time: 10:00 - 12:00
Place: CELC 404

Speaker: Kazuhisa Makino (Univ. of Kyoto)
Title: Posimodular function optimization
Abstract:
Given a posimodular function f: 2^V \to \mathbb{R} on a finite set V, we
 consider the problem of finding a nonempty subset X of V that minimizes
 f(X). Posimodular functions often arise in combinatorial optimization such
 as undirected cut functions. In this paper, we show that any algorithm for
 the problem requires \Omega(2^{\frac{n}{7.54}}) oracle calls to f, where
 n=|V|. It contrasts to the fact that the submodular function minimization,
 which is another generalization of cut functions, is polynomially solvable.
 When the range of a given posimodular function is restricted to be
 D=\{0,1,...,d\} for some nonnegative integer d, we show that
 \Omega(2^{\frac{d}{15.08}}) oracle calls are necessary, while we propose an
 O(n^dT_f+n^{2d+1})-time algorithm for the problem. Here, T_f denotes the
 time needed to evaluate the function value f(X) for a given X \subseteq V.
 We also consider the problem of maximizing a given posimodular function. We
 show that \Omega(2^{n-1}) oracle calls are necessary for solving the
 problem, and that the problem has time complexity \Theta(n^{d-1}T_f) when
 D=\{0,1,..., d\} is the range of f for some constant d.

 This is a joint work with Toshimasa Ishii.