The complexity of recognizing linear systems with certain integrality properties

DOI10.1007/s10107-007-0103-yzbMath1160.90633OpenAlexW2075710886MaRDI QIDQ927158

Li Feng, Guoli Ding, Wenan Zang

Publication date: 4 June 2008

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

Full work available at URL: http://hdl.handle.net/10722/58972

zbMATH Keywords

NP-hardnessLinear systemPolyhedronTotal dual integrality

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items

An extension of Lehman's theorem and ideal set functions, Delta Minors, Delta Free Clutters, and Entanglement, Clean Clutters and Dyadic Fractional Packings, Total dual dyadicness and dyadic generating sets, Intersecting and dense restrictions of clutters in polynomial time, Intersecting restrictions in clutters, Co-density and fractional edge cover packing, Testing additive integrality gaps, Counting vertices of integral polytopes defined by facets, Trader multiflow and box-TDI systems in series-parallel graphs, Characterizing and recognizing generalized polymatroids, Sparse recovery with integrality constraints, Alternatives for testing total dual integrality, Non total-unimodularity neutralized simplicial complexes, The negative cycles polyhedron and hardness of checking some polyhedral properties, Total dual integrality of the linear complementarity problem, Recognizing conic TDI systems is hard, Box-total dual integrality, box-integrality, and equimodular matrices, When Is the Matching Polytope Box-Totally Dual Integral?, Testing idealness in the filter oracle model, Universally balanced combinatorial optimization games

Cites Work

• The strong perfect graph theorem
• The matroids with the max-flow min-cut property
• On certain polytopes associated with graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Recognizing Berge graphs
• Normal hypergraphs and the perfect graph conjecture
• Combinatorial Optimization
• A polynomial-time test for total dual integrality in fixed dimension
• Blocking and anti-blocking pairs of polyhedra
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item