A bad network problem for the simplex method and other minimum cost flow algorithms
From MaRDI portal
Publication:4775712
DOI10.1007/BF01580132zbMath0287.90030MaRDI QIDQ4775712
Publication date: 1973
Published in: Mathematical Programming (Search for Journal in Brave)
90C35: Programming involving graphs or networks
90B10: Deterministic network models in operations research
Related Items
A comprehensive simplex-like algorithm for network optimization and perturbation analysis, Algorithms, The complexity of linear programming, A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time, Multiple objective minimum cost flow problems: a review, Approximating earliest arrival flows with flow-dependent transit times, An exterior simplex type algorithm for the minimum cost network flow problem, Penelope's graph: a hard minimum cost tension instance, On relaxation methods for systems of linear inequalities, On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem, Finding minimum-cost flows by double scaling, Algorithms for the minimum cost circulation problem based on maximizing the mean improvement, Efficient search for rationals, A method for convex curve approximation, Efficient continuous-time dynamic network flow algorithms, Tight bounds on the number of minimum-mean cycle cancellations and related results, Random walks, totally unimodular matrices, and a randomised dual simplex algorithm, Minimizing a linear multiplicative-type function under network flow constraints, A polynomial time primal network simplex algorithm for minimum cost flows, The inverse-parametric knapsack problem, Fast finite methods for a system of linear inequalities, Approximation of convex curves with application to the bicriterial minimum cost flow problem, The ellipsoid method and its implications, A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks, On the length of simplex paths: The assignment case, Complexity of some parametric integer and network programming problems, Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh, Parametric maximal flows in generalized networks – complexity and algorithms, Algorithms for flows with parametric capacities, The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm, The quickest flow problem, A network simplex method, Some experiments with the pathological linear programs of N. Zadeh
Cites Work
- On a Class of Capacitated Transportation Problems
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- More pathological examples for network flow problems
- A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
- Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows
- On some techniques useful for solution of transportation network problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
