Towards Minimizing k-Submodular Functions
Towards Minimizing k-Submodular Functions
复制标题
迈向最小化 k 子模函数
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
V. Kolmogorov
中科院分区：
文献类型：
--
作者：
Anna Huber;V. Kolmogorov
本文研究k-次模函数。这个离散函数的自然族包括子模函数和双子模函数，分别作为特殊情况k=1和k=2。
特别是，我们推广了已知的最小最大定理的次模和bisubummodular功能。该定理断言（bi）子模函数的最小值可以通过求解（bi）子模多面体上的最大化问题来找到。定义了k-次模多面体，证明了k-次模函数的一个极大极小定理，并给出了构造该多面体顶点的贪婪算法。
In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k=1 and k=2 respectively.
In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.