Combinatorial Optimization
Combinatorial Optimization
复制标题
组合优化
DOI：
10.1007/978-3-642-32147-4_40
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Huber A
中科院分区：
文献类型：
--
作者：
Huber A
本文研究了次模函数。在k= 1和k= 2的特殊情况下，离散函数的自然族包括次模函数和双模函数。特别地，我们推广了已知的次模和双次模函数的最小极大定理。这个定理断言（bi）次模函数的最小值可以通过求解（bi）次模多面体上的最大化问题来找到。定义了ak-次模多面体，证明了一个最小-极大定理叉-次模函数，给出了构造多面体顶点的贪心算法。
In this paper we investigatek-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special casesk= 1 andk= 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 ak-submodular polyhedron, prove a Min-Max-Theorem fork-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.