Monge and feasibility sequences in general flow problems
From MaRDI portal
Publication:686244
DOI10.1016/0166-218X(93)90220-IzbMath0780.90028MaRDI QIDQ686244
Alan J. Hoffman, Ilan Adler, Ron Shamir
Publication date: 23 January 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Applications of graph theory (05C90) Abstract computational complexity for mathematical programming problems (90C60) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Deterministic network models in operations research (90B10)
Related Items
Permuting matrices to avoid forbidden submatrices, Perspectives of Monge properties in optimization, On some properties of DNA graphs, Sparse Monge matrices arising from scheduling problems, A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs, EMDUniFrac: exact linear time computation of the UniFrac metric and identification of differentially abundant organisms, A fast bipartite network flow algorithm for selective assembly, Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monge sequences, antimatroids, and the transportation problem with forbidden arcs
- Minimizing the number of tardy job units under release time constraints
- Characterizations of strongly chordal graphs
- Recognition of Gilmore-Gomory traveling salesman problem
- Geometric applications of a matrix-searching algorithm
- An algorithm for the detection and construction of Monge sequences
- The complexity of one-machine batching problems
- Parallel searching in generalized Monge arrays
- Doubly lexical ordering of dense 0--1 matrices
- Betweenness, orders and interval graphs
- Totally-Balanced and Greedy Matrices
- On Transportation Problems with Upper Bounds on Leading Rectangles
- Doubly Lexical Orderings of Matrices
- Three Partition Refinement Algorithms
- New Bounds on the Complexity of the Shortest Path Problem
- Fibonacci heaps and their uses in improved network optimization algorithms
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
- A Noniterative Algorithm for Tridiagonal Transportation Problems and Its Generalization
- Depth-First Search and Linear Graph Algorithms
