On the complexity of recognizing integrality and total dual integrality of the {0,1/2}-closure

Matthias Brugger, Andreas S. Schulz

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

1 Zitat (Scopus)

Abstract

The [Formula presented]-closure of a rational polyhedron {x:Ax≤b} is obtained by adding all Gomory-Chvátal cuts that can be derived from the linear system Ax≤b using multipliers in [Formula presented]. We show that deciding whether the [Formula presented]-closure coincides with the integer hull is strongly NP-hard. A direct consequence of our proof is that, testing whether the linear description of the [Formula presented]-closure derived from Ax≤b is totally dual integral, is strongly NP-hard.

OriginalspracheEnglisch
Seiten (von - bis)16-19
Seitenumfang4
FachzeitschriftOperations Research Letters
Jahrgang50
Ausgabenummer1
DOIs
PublikationsstatusVeröffentlicht - Jan. 2022

Fingerprint

Untersuchen Sie die Forschungsthemen von „On the complexity of recognizing integrality and total dual integrality of the {0,1/2}-closure“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren