Time: 2:00pm Monday 23rd February.

Location: SIT 459

Speaker: A. Prof. Kazuhisa Makino, Kyoto Univeristy

Title: Posimodular Function Optimization

Abstract:

Given a posimodular function f:2^V→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 talk, we show that any algorithm for the problem requires Ω(2^{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 Ω(2^{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⊆V.

We also consider the problem of maximizing a given posimodular function. We show that Ω(2^{n−1}) oracle calls are necessary for solving the problem, and that the problem has time complexity Θ(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 (Hokkaido Univ).

### Like this:

Like Loading...

*Related*

## Discussion

## No comments yet.