Text

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.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.2 May 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1026-1047

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

TOTAL DUAL INTEGRALITY
MIN-MAX FORMULA
DISCRETE CONVEX FUNCTION
COMBINATORIAL INVERSE PROBLEM
INTEGRAL BASE-POLYHEDRON
M-CONVEX SET

Info Detail Spesifik

https://doi.org/10.1287/moor.2021.1160

Pernyataan Tanggungjawab

András Frank, Kazuo Murota

Versi lain/terkait

Lampiran Berkas

Komentar