Integral infeasibility and testing total dual integrality
type: Item
instance of: scholarly article
title: Integral infeasibility and testing total dual integrality
zbMATH Open document ID: 0722.90057
DOI: 10.1016/0167-6377(91)90084-3
author: David Applegate
author: William Cook
author: S. Thomas McCormick
published in: Operations Research Letters
publication date: 1991-01-01T00:00:00Z
review text: A systematic method is introduced to determine the total dual integrality of a linear system and it is used successfully to a problem concerning feedback sets in directed graphs. This method can be used only for relatively small problems. As the size of the problem increases, this method becomes unrealistic.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 93C05
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 4191406
zbMATH Keywords: polyhedra
zbMATH Keywords: total dual integrality
zbMATH Keywords: linear system
zbMATH Keywords: feedback sets in directed graphs
MaRDI profile type: Publication
full work available at URL: 0167-6377(91)90084-3
OpenAlex ID: W2093283678
cites work: Polynomial Algorithms for Totally Dual Integral Systems and Extensions
cites work: Total weak unimodularity: Testing and applications
cites work: A polynomial-time test for total dual integrality in fixed dimension
cites work: Q4149476
cites work: Finding feasible vectors of Edmonds-Giles polyhedra
cites work: Total dual integrality and integer polyhedra
cites work: Q3274170
cites work: A generalization of max flow—min cut
cites work: Q3221421
cites work: Integer Programming with a Fixed Number of Variables
cites work: Matching theory
cites work: A Minimax Theorem for Directed Graphs
cites work: Q3818127
Recommended article: Alternatives for testing total dual integrality
Recommended article: A polynomial-time test for total dual integrality in fixed dimension
Recommended article: Intractability results for integration and discrepancy
Recommended article: Characterizations of Total Dual Integrality
Recommended article: Q3220355
Recommended article: Total dual integrality of the linear complementarity problem
Recommended article: Total dual integrality and integral solutions of the linear complementarity problem
Recommended article: An intractability result for multiple integration
Recommended article: On Testing Integrability
Recommended article: On totally dual integral systems
description: scientific article; zbMATH DE number 4191406