A Min-Max Theorem for Bisubmodular Polyhedra
A Min-Max Theorem for Bisubmodular Polyhedra
复制标题
双亚模多面体的最小-最大定理
DOI：
10.1137/s0895480194264344
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
S. Fujishige
中科院分区：
文献类型：
--
作者：
S. Fujishige
对于族 ${\cal F} \subseteq 3^E$ 相对于约简并集和交集闭合，以及对于双子模函数 $f: {\cal F}\rightarrow \mbox{\bf R}$ 和 $(\emptyset,\emptyset) \in \cal F$ 且 $f(\emptyset,\emptyset)=0$，给出与 $({\cal F},f)$ 关联的双子模多面体由 \[ {\rm P}_*(f)=\{x\,|\,x\in\mbox{\bf R}^E\quad \forall (X,Y)\in {\cal F}: x(X,Y)\le f(X,Y)\}, \] 其中 $x(X,Y)=\sum_{e\in X}x(e)-\sum_{e\in Y}x(e)$。我们展示了一个最小-最大关系，它描述了 ${\rm P}_*(f)$ 和给定点 $x^0$ 之间相对于 $l_1$ 范数的距离：对于任何向量 $x^0\in\mbox{\bf R}^E$，\[ \left。 \min\left\{\sum_{e\in E}|x(e)-x^0(e)|\, \right| \,x\in{\rm P}_*(f)\right\} =\max\{x^0(X,Y)-f(X,Y)\,|\,(X,Y)\in{\cal F}\}, \] 其中，如果 $f$ 为整数值且 $x^0$ 为积分，则通过积分 $x\in{\rm P}_*(f)$ 获得最小值。这在某种意义上相当于但比 Cunningham 和 Green-Krotki [Combinatorica, 11 (1991), pp. 219--230] 的最小-最大定理更好的对称形式，该定理被证明与 $b$ 匹配度序列多面体相关，并且概括了有关多拟阵和子模系统向量约简的众所周知的最小-最大定理。我们还将该定理应用于双子模多面体上的可分离凸优化问题。
For a family ${\cal F} \subseteq 3^E$ closed with respect to the reduced union and intersection and for a bisubmodular function $f: {\cal F}\rightarrow \mbox{\bf R}$ with $(\emptyset,\emptyset) \in \cal F$ and $f(\emptyset,\emptyset)=0$, the bisubmodular polyhedron associated with $({\cal F},f)$ is given by \[ {\rm P}_*(f)=\{x\,|\,x\in\mbox{\bf R}^E\quad \forall (X,Y)\in {\cal F}: x(X,Y)\le f(X,Y)\}, \] where $x(X,Y)=\sum_{e\in X}x(e)-\sum_{e\in Y}x(e)$. We show a min--max relation that characterizes the distance between ${\rm P}_*(f)$ and a given point $x^0$ with respect to the $l_1$ norm: for any vector $x^0\in\mbox{\bf R}^E$, \[ \left. \min\left\{\sum_{e\in E}|x(e)-x^0(e)|\, \right| \,x\in{\rm P}_*(f)\right\} =\max\{x^0(X,Y)-f(X,Y)\,|\,(X,Y)\in{\cal F}\}, \] where if $f$ is integer valued and $x^0$ is integral, then the minimum is attained by an integral $x\in{\rm P}_*(f)$. This is in a sense equivalent to but is in a nicer symmetric form than a min--max theorem of Cunningham and Green-Krotki [Combinatorica, 11 (1991), pp. 219--230] shown to be associated with $b$-matching degree-sequence polyhedra and generalizes the well-known min--max theorem concerning a vector reduction of polymatroids and submodular systems. We also give an application of the theorem to a separable convex optimization problem on bisubmodular polyhedra.