Non-TDI graph-optimization with supermodular functions (extended abstract)

Kristóf Bérczi, András Frank


Total dual integrality (TDI-ness) is a major concept in attacking various combinatorial optimization problems. Here we develop several new min-max theorems and good characterizations in graph theory where the minimum cost extension is already NP-complete, implying that such problems cannot be described by TDI linear systems. The main device is a min-max theorem of Frank and Jord\'an on covering a supermodular function by digraphs.

Bibtex entry:

AUTHOR = {B{\'e}rczi, Krist{\'o}f and Frank, Andr{\'a}s},
TITLE = {Non-TDI graph-optimization with supermodular functions (extended abstract)},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-14}

Last modification: 29.12.2020. Please email your comments to Tamás Király!