TR-2015-14

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

Kristóf Bérczi, András Frank



Abstract

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:

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


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