Monge and feasibility sequences in general flow problems

DOI10.1016/0166-218X(93)90220-IMaRDI QIDQ686244zbMATH OpenFDO

Authors Ilan Adler, Alan J. Hoffman, Ron Shamir

Publication date 23 January 1994

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

chordal bipartite graphstransshipmenttotally balanced matricesMonge sequences

Mathematics Subject Classification ID

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)

Recommendations

• Generalization of a theorem on the parametric maximum flow problem
• Minimizing Flows for the Monge--Kantorovich Problem
• Combinatorial approximation algorithms for generalized flow problems
• A Dacorogna-Moser approach to flow decomposition and minimal flow problems
• The complementary class of generalized flow cover inequalities
• scientific article; zbMATH DE number 1136259
• scientific article; zbMATH DE number 125039
• scientific article; zbMATH DE number 1127062
• Monge sequences, antimatroids, and the transportation problem with forbidden arcs
• On maximum flows in polyhedral domains

Cites work

• scientific article; zbMATH DE number 432782 (Why is no real title available?)
• scientific article; zbMATH DE number 3167494 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 3272833 (Why is no real title available?)
• A Noniterative Algorithm for Tridiagonal Transportation Problems and Its Generalization
• An algorithm for the detection and construction of Monge sequences
• Betweenness, orders and interval graphs
• Characterizations of strongly chordal graphs
• Depth-First Search and Linear Graph Algorithms
• Doubly Lexical Orderings of Matrices
• Doubly lexical ordering of dense 0--1 matrices
• Fibonacci heaps and their uses in improved network optimization algorithms
• Geometric applications of a matrix-searching algorithm
• Minimizing the number of tardy job units under release time constraints
• Monge sequences, antimatroids, and the transportation problem with forbidden arcs
• New Bounds on the Complexity of the Shortest Path Problem
• On Transportation Problems with Upper Bounds on Leading Rectangles
• Parallel searching in generalized Monge arrays
• Recognition of Gilmore-Gomory traveling salesman problem
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• The complexity of one-machine batching problems
• Three Partition Refinement Algorithms
• Totally-Balanced and Greedy Matrices

Cited in

(11)

• On some properties of DNA graphs
• An algorithm for the detection and construction of Monge sequences
• A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
• scientific article; zbMATH DE number 427738 (Why is no real title available?)
• Permuting matrices to avoid forbidden submatrices
• Monge sequences, antimatroids, and the transportation problem with forbidden arcs
• Sparse Monge matrices arising from scheduling problems
• Perspectives of Monge properties in optimization
• Monge properties, optimal greedy policies, and policy improvement for the dynamic stochastic transportation problem
• EMDUniFrac: exact linear time computation of the UniFrac metric and identification of differentially abundant organisms
• A fast bipartite network flow algorithm for selective assembly

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)