论文标题
Box-TDI Polyhedra的离散凸Min-Max公式
A Discrete Convex Min-Max Formula for Box-TDI Polyhedra
论文作者
论文摘要
最小值可分开的离散凸功能证明了最小值公式，其中最小值是在盒子总二个积分（box-tdi）polyhedron的集成元素集中。定理的一种变体使用共轭函数的概念（非线性优化中的基本概念），但我们还提供了另一个避免结合物的版本，其精神在概念上更接近了在组合优化中经典的Min-Max定理的标准形式。提出的框架为两个积分基碱，supperlohedra，submodular流，L-convex集和Polyhedra的相互作用集提供了可分离凸的统一背景。作为一个意外的应用程序，我们展示了该新框架如何涵盖一系列广泛的逆组合优化问题。
A min-max formula is proved for the minimum of an integer-valued separable discrete convex function where the minimum is taken over the set of integral elements of a box total dual integral (box-TDI) polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in non-linear 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 (TU) matrices. As an unexpected application, we show how a wide class of inverse combinatorial optimization problems can be covered by this new framework.
