A Discrete Convex Min-Max Formula for Box-TDI Polyhedra
证明了在盒式全对偶整数多面体的整数点上最小化可分离散凸函数的一个极小极大公式，为逆组合优化问题提供了统一框架。
A min-max formula is proved for the minimum of an integer-valued separable discrete convex function in which the minimum is taken over the set of integral elements of a box total dual integral polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in nonlinear optimization), but we also provide another version that avoids conjugates, and its spirit is conceptually closer to the standard form of classic min-max theorems in combinatorial optimization. The presented framework provides a unified background for separable convex minimization over the set of integral elements of the intersection of two integral base-polyhedra, submodular flows, L-convex sets, and polyhedra defined by totally unimodular matrices. As an unexpected application, we show how a wide class of inverse combinatorial optimization problems can be covered by this new framework.