Monge and feasibility sequences in general flow problems
DOI10.1016/0166-218X(93)90220-IzbMATH Open0780.90028MaRDI QIDQ686244FDOQ686244
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) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60) 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?)
- Fibonacci heaps and their uses in improved network optimization algorithms
- Depth-First Search and Linear Graph Algorithms
- Doubly lexical ordering of dense 0--1 matrices
- Three Partition Refinement Algorithms
- Characterizations of strongly chordal graphs
- Geometric applications of a matrix-searching algorithm
- The complexity of one-machine batching problems
- Parallel searching in generalized Monge arrays
- Totally-Balanced and Greedy Matrices
- Doubly Lexical Orderings of Matrices
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
- Minimizing the number of tardy job units under release time constraints
- Recognition of Gilmore-Gomory traveling salesman problem
- New Bounds on the Complexity of the Shortest Path Problem
- Betweenness, orders and interval graphs
- An algorithm for the detection and construction of Monge sequences
- On Transportation Problems with Upper Bounds on Leading Rectangles
- Monge sequences, antimatroids, and the transportation problem with forbidden arcs
- A Noniterative Algorithm for Tridiagonal Transportation Problems and Its Generalization
Cited In (9)
- Sparse Monge matrices arising from scheduling problems
- A fast bipartite network flow algorithm for selective assembly
- Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem
- On some properties of DNA graphs
- A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
- Perspectives of Monge properties in optimization
- Title not available (Why is that?)
- EMDUniFrac: exact linear time computation of the UniFrac metric and identification of differentially abundant organisms
- Permuting matrices to avoid forbidden submatrices
Recommendations
- Minimizing Flows for the Monge--Kantorovich Problem 👍 👎
- A dacorogna-moser approach to flow decomposition and minimal flow problems 👍 👎
- The complementary class of generalized flow cover inequalities 👍 👎
- Combinatorial approximation algorithms for generalized flow problems 👍 👎
- On maximum flows in polyhedral domains 👍 👎
- Generalization of a theorem on the parametric maximum flow problem 👍 👎
- Monge sequences, antimatroids, and the transportation problem with forbidden arcs 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
This page was built for publication: Monge and feasibility sequences in general flow problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686244)
