Department of
Applied
Mathematics

Posimodular Function Optimization

Kazuhisa Makino

RIMS, Kyoto University

Abstract

(joint work with Magnus M. Halldorsson (Reykjavik University), Toshimasa Ishii (Hokkaido University), and Kenjiro Takazawa (Hosei University))

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), given by oracle access. Posimodular functions often arise in combinatorial optimization such as undirected cut functions.

We show that posimodular function minimization requires exponential time, contrasting with the polynomial solvability of submodular function minimization that forms another generalization of cut functions. On the other hand, the problem is fixed-parameter tractable in terms of the size of the image (or range) of f.

In more detail, we show that Omega(2^{0.3219n} T_f) time is necessary and O(2^{0.92n}T_f) sufficient, where T_f denotes the time for one function evaluation. When the image of f is D={0,1,...,d}, O(2^{1.217d}nT_f) time is sufficient and Omega(2^{0.1609d}T_f) necessary. We can also generate all sets minimizing f in time 2^{O(d)}n^2T_f.

Finally, we also consider the problem of maximizing a given posimodular function, showing that it requires at least 2^{n-1}T_f time in general, while it has time complexity Theta(n^{d-1}T_f) when D={0,1,..., d} is the image of f, for integer d.