An algorithm for the detection and construction of Monge sequences

DOI10.1016/0024-3795(89)90487-4MaRDI QIDQ1116656zbMATH OpenOpenAlexFDO

Authors Steven Cosares, Dorit S. Hochbaum, Ron Shamir, Noga Alon

Publication date 1989

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(89)90487-4

zbMATH Keywords

greedy algorithmtransportation problemMonge sequence

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• 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

Cites work

• 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?)
• A Noniterative Algorithm for Tridiagonal Transportation Problems and Its Generalization
• 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

Cited in

(23)

• Minimizing the number of tardy job units under release time constraints
• An Algebraic Construction of Sonar Sequences Using M-Sequences
• On the recognition of permuted bottleneck Monge matrices
• Planning for end-user substitution in agribusiness
• A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
• Permuting matrices to avoid forbidden submatrices
• On Monge sequences in \(d\)-dimensional arrays
• Weak Monge arrays in higher dimensions
• Monge and feasibility sequences in general flow problems
• Monge sequences, antimatroids, and the transportation problem with forbidden arcs
• Recognition of \(d\)-dimensional Monge arrays
• The \(S\)-digraph optimization problem and the greedy algorithm
• Monge sequences and a simple assignment algorithm
• Sparse Monge matrices arising from scheduling problems
• Inventory allocation with full downward substitution and monotone cost differences
• Some recent results in the analysis of greedy algorithms for assignment problems
• Allocation under a general substitution structure
• Perspectives of Monge properties in optimization
• Monge properties, discrete convexity and applications
• Monge properties, optimal greedy policies, and policy improvement for the dynamic stochastic transportation problem
• An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays
• Optimal couplings are totally positive and more
• Recognition of overlap graphs

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)