you're reading...

SACT Seminar: Posimodular Function Optimization

Time: 2:00pm Monday 23rd February.

Location: SIT 459

Speaker: A. Prof. Kazuhisa Makino, Kyoto Univeristy

Title: Posimodular Function Optimization


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).



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 61 other followers

%d bloggers like this: