A Discrete Convex Min-Max Formula for Box-TDI Polyhedra
成果类型：
Article
署名作者：
Frank, Andras; Murota, Kazuo
署名单位：
Eotvos Lorand University; Tokyo Metropolitan University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2021.1160
发表日期：
2022
页码：
1026-1047
关键词：
摘要：
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.
来源URL：