A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs

DOI10.1016/0012-365X(93)90382-4zbMath0799.90093MaRDI QIDQ685703

Ron Shamir

Publication date: 24 October 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

transportation problemMonge sequence

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (11)

On the recognition of permuted bottleneck Monge matrices ⋮ The assignment problem with nearly Monge arrays and incompatible partner indices ⋮ Technical Note—A Monge Sequence-Based Approach to Characterize the Competitive Newsvendor Problem ⋮ On Monge sequences in \(d\)-dimensional arrays ⋮ Perspectives of Monge properties in optimization ⋮ Avoiding unnecessary demerging and remerging of multi‐commodity integer flows ⋮ Inventory allocation with full downward substitution and monotone cost differences ⋮ Monge properties, discrete convexity and applications ⋮ Monge sequences, antimatroids, and the transportation problem with forbidden arcs ⋮ Allocation under a general substitution structure ⋮ Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem

Cites Work

• Monge and feasibility sequences in general flow problems
• On the Monge property of matrices
• Monge sequences, antimatroids, and the transportation problem with forbidden arcs
• Minimizing the number of tardy job units under release time constraints
• Recognition of Gilmore-Gomory traveling salesman problem
• An algorithm for the detection and construction of Monge sequences
• Recognition of \(d\)-dimensional Monge arrays
• A Monge property for the \(d\)-dimensional transportation problem
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs