An algorithm for the detection and construction of Monge sequences
DOI10.1016/0024-3795(89)90487-4zbMATH Open0666.65044OpenAlexW2045879812MaRDI QIDQ1116656FDOQ1116656
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
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
Numerical mathematical programming methods (65K05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
- Recognition of Gilmore-Gomory traveling salesman problem
- Title not available (Why is that?)
- On Transportation Problems with Upper Bounds on Leading Rectangles
- A Noniterative Algorithm for Tridiagonal Transportation Problems and Its Generalization
Cited In (23)
- Monge and feasibility sequences in general flow problems
- Monge properties, discrete convexity and applications
- Recognition of overlap graphs
- Monge sequences, antimatroids, and the transportation problem with forbidden arcs
- On Monge sequences in \(d\)-dimensional arrays
- Monge sequences and a simple assignment algorithm
- Sparse Monge matrices arising from scheduling problems
- An Algebraic Construction of Sonar Sequences Using M-Sequences
- Optimal couplings are totally positive and more
- An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays
- Some recent results in the analysis of greedy algorithms for assignment problems
- The \(S\)-digraph optimization problem and the greedy algorithm
- Allocation under a general substitution structure
- Planning for end-user substitution in agribusiness
- Minimizing the number of tardy job units under release time constraints
- A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
- Perspectives of Monge properties in optimization
- Weak Monge arrays in higher dimensions
- Monge properties, optimal greedy policies, and policy improvement for the dynamic stochastic transportation problem
- Recognition of \(d\)-dimensional Monge arrays
- Inventory allocation with full downward substitution and monotone cost differences
- On the recognition of permuted bottleneck Monge matrices
- Permuting matrices to avoid forbidden submatrices
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)
