Total weak unimodularity: Testing and applications

DOI10.1016/0012-365X(84)90067-0MaRDI QIDQ798401zbMATH OpenFDO

Authors R. Chandrasekaran, S. Shirali

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(84)90067-0

zbMATH Keywords

Hilbert propertyintegral vectorpolynomially bounded algorithmtotally weakly unimodular

Mathematics Subject Classification ID

Miscellaneous inequalities involving matrices (15A45) Matrices of integers (15B36)

Review text

An integer matrix is called totally weakly unimodular (TWU) if the following statement is true for all integral b: There exists x such that A\(x\geq b\) implies there exists integral x such that A\(x\geq b\). A polynomially bounded algorithm is presented that either produces an integral x satisfying A\(x\geq b\) or shows that A is not TWU for an integral matrix A and an integral vector b.

Recommendations

• scientific article; zbMATH DE number 221298
• Two simple applications of the unmodularity property
• On a Class of Totally Unimodular Matrices
• A direct constructive proof of a known result on total unimodularity, and a characterisation of related partitions
• A decomposition theory for matroids. V: Testing of matrix total unimodularity

Cites work

• A generalization of max flow—min cut
• Balanced matrices
• Blocking and anti-blocking pairs of polyhedra
• Cyclic Scheduling via Integer Programs with Circular Ones
• Dual integrality in b-matching problems
• Finite checkability for integer rounding properties in combinatorial programming problems
• scientific article; zbMATH DE number 3661345 (Why is no real title available?)
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 3323651 (Why is no real title available?)
• Matroids and the greedy algorithm
• Minimum partition of a matroid into independent subsets
• On total dual integrality
• Packing rooted directed cuts in a weighted directed graph
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Polynomial Algorithms for Totally Dual Integral Systems and Extensions
• Some Basis Theorems for Integral Monoids
• The matroids with the max-flow min-cut property
• Two-commodity cut-packing problem

Cited in

(6)

• Two simple applications of the unmodularity property
• Implementation of a unimodularity test
• Totally unimodular stochastic programs
• Total dual integrality implies local strong unimodularity
• scientific article; zbMATH DE number 221298 (Why is no real title available?)
• Integral infeasibility and testing total dual integrality

This page was built for publication: Total weak unimodularity: Testing and applications

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