Recognizing conic TDI systems is hard

DOI10.1007/S10107-009-0294-5MaRDI QIDQ543398zbMATH OpenOpenAlexFDO

Authors Júlia Pap

Publication date 17 June 2011

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-009-0294-5

zbMATH Keywords

Hilbert basistotally dual integral

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The complexity of recognizing linear systems with certain integrality properties
• Publication:4941892
• A polynomial-time test for total dual integrality in fixed dimension
• Alternatives for testing total dual integrality
• On recognizing integer polyhedra

Cites work

• A polynomial-time test for total dual integrality in fixed dimension
• scientific article; zbMATH DE number 3885657 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• The complexity of recognizing linear systems with certain integrality properties
• The height of minimal Hilbert bases
• Total dual integrality and integer polyhedra

Cited in

(14)

• Total dual integrality of the linear complementarity problem
• Box-total dual integrality, box-integrality, and equimodular matrices
• Total dual dyadicness and dyadic generating sets
• Trader multiflow and box-TDI systems in series-parallel graphs
• Alternatives for testing total dual integrality
• On recognizing integer polyhedra
• Testing additive integrality gaps
• Characterizing and recognizing generalized polymatroids
• scientific article; zbMATH DE number 1418330 (Why is no real title available?)
• On the complexity of recognizing the Hilbert basis of a linear Diophantine system
• Total dual dyadicness and dyadic generating sets
• Hard problems on box-totally dual integral polyhedra
• The length polyhedron of an interval order
• The complexity of recognizing linear systems with certain integrality properties

This page was built for publication: Recognizing conic TDI systems is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q543398)