An algorithm for the detection and construction of Monge sequences
\textit{A. J. Hoffman} [Proc. Symp. Pure Math. 7, 317-327 (1963; Zbl 0171.178)] proved that a transportation problem can be solved by a greedy algorithm if there exists a sequence (called Monge sequence) of pairs of indices of the cost matrix \(C=(c_{ij})\) such that if (i,j) preceeds both (i,s) and (r,j), then \(c_{ij}+c_{rs}\leq c_{is}+c_{rj}.\) The authors describe a general algorithm which generates a Monge sequence whenever it exists and prove that for an \(m\times n\) matrix \({\mathcal C}\) it requires \(O(\bar m^ 2\bar n \log \bar n)\) time and \(O(\bar m^ 2\bar n)\) space where \(\bar m=\min (m,n)\) and \(\bar n=\max (m,n).\)
- On Monge sequences in \(d\)-dimensional arrays
- A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
- A Monge property for the \(d\)-dimensional transportation problem
- Sparse Monge matrices arising from scheduling problems
- Monge and feasibility sequences in general flow problems
- A Noniterative Algorithm for Tridiagonal Transportation Problems and Its Generalization
- scientific article; zbMATH DE number 3167494 (Why is no real title available?)
- scientific article; zbMATH DE number 4027206 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3099866 (Why is no real title available?)
- On Transportation Problems with Upper Bounds on Leading Rectangles
- Recognition of Gilmore-Gomory traveling salesman problem
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
- Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
- The \(S\)-digraph optimization problem and the greedy algorithm
- Monge sequences and a simple assignment algorithm
- Some recent results in the analysis of greedy algorithms for assignment problems
- Recognition of \(d\)-dimensional Monge arrays
- On Monge sequences in \(d\)-dimensional arrays
- Spanning trees and shortest paths in Monge graphs
- Weak Monge arrays in higher dimensions
- Allocation under a general substitution structure
- Permuting matrices to avoid forbidden submatrices
- On the recognition of permuted bottleneck Monge matrices
- Perspectives of Monge properties in optimization
- Monge properties, discrete convexity and applications
- Sparse Monge matrices arising from scheduling problems
- An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays
- Planning for end-user substitution in agribusiness
- An Algebraic Construction of Sonar Sequences Using M-Sequences
- Recognition of overlap graphs
- Optimal couplings are totally positive and more
- Monge properties, optimal greedy policies, and policy improvement for the dynamic stochastic transportation problem
- Inventory allocation with full downward substitution and monotone cost differences
- A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
- Monge and feasibility sequences in general flow problems
- Monge sequences, antimatroids, and the transportation problem with forbidden arcs
- Minimizing the number of tardy job units under release time constraints
This page was built for publication: An algorithm for the detection and construction of Monge sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116656)
