Sparse dual transportation polyhedra: Extreme points and signatures

DOI10.1016/0167-6377(90)90050-FMaRDI QIDQ911458zbMATH OpenOpenAlexFDO

Authors J. González

Publication date 1990

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(90)90050-f

zbMATH Keywords

best upper bounddual transportation polyhedranumber of extreme points

Mathematics Subject Classification ID

Trees (05C05) Polytopes and polyhedra (52Bxx) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Programming involving graphs or networks (90C35)

Review text

For dual transportation polyhedra \(D_{m,n}(c)=\{(u,v)|\) \(u_ i+v_ j\leq c_{ij}\), \(u_ 1=0\}\), where c is a sparse \(m\times n\) matrix, a characterization of the extreme points is given via spanning tree signatures of the associated bipartite graph to c. The characterization is used to derive a best upper bound of the number of extreme points of such a polyhedron.

Recommendations

• Faces of dual transportation polyhedra
• Adjacent Extreme Points Of A Transportation Polytope
• The Hirsch Conjecture for Dual Transportation Polyhedra
• Extreme points of certain transportation polytopes with fixed total sums
• On the circuit diameter of dual transportation polyhedra

Cites work

• A competitive (dual) simplex method for the assignment problem
• Efficient dual simplex algorithms for the assignment problem
• Faces of dual transportation polyhedra
• scientific article; zbMATH DE number 3127542 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• Signature Methods for the Assignment Problem
• The Hirsch Conjecture for Dual Transportation Polyhedra
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems

Cited in

(3)

• Faces of dual transportation polyhedra
• scientific article; zbMATH DE number 1929288 (Why is no real title available?)
• Signature classes of transportation polytopes

This page was built for publication: Sparse dual transportation polyhedra: Extreme points and signatures

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