A bad network problem for the simplex method and other minimum cost flow algorithms

DOI10.1007/BF01580132zbMath0287.90030OpenAlexW2092572272MaRDI QIDQ4775712

Publication date: 1973

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580132

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items

On the length of simplex paths: The assignment case ⋮ Random walks, totally unimodular matrices, and a randomised dual simplex algorithm ⋮ The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm ⋮ Algorithms for Flows over Time with Scheduling Costs ⋮ A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks ⋮ Complexity of some parametric integer and network programming problems ⋮ Smoothed Analysis of the Successive Shortest Path Algorithm ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ Multiple objective minimum cost flow problems: a review ⋮ Minimizing a linear multiplicative-type function under network flow constraints ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ Approximating earliest arrival flows with flow-dependent transit times ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ Penelope's graph: a hard minimum cost tension instance ⋮ The inverse-parametric knapsack problem ⋮ The quickest flow problem ⋮ Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh ⋮ An Introduction to Network Flows over Time ⋮ On relaxation methods for systems of linear inequalities ⋮ Algorithms ⋮ On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem ⋮ Parametric maximal flows in generalized networks – complexity and algorithms ⋮ Finding minimum-cost flows by double scaling ⋮ Algorithms for flows with parametric capacities ⋮ An exterior simplex type algorithm for the minimum cost network flow problem ⋮ Algorithms for the minimum cost circulation problem based on maximizing the mean improvement ⋮ The complexity of linear programming ⋮ A network simplex method ⋮ A heuristic algorithm for the earliest arrival flow with multiple sources ⋮ The diameters of network-flow polytopes satisfy the Hirsch conjecture ⋮ Some experiments with the pathological linear programs of N. Zadeh ⋮ A Stackelberg strategy for routing flow over time ⋮ Finding non-dominated solutions in bi-objective integer network flow problems ⋮ Efficient search for rationals ⋮ A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time ⋮ Fast finite methods for a system of linear inequalities ⋮ A method for convex curve approximation ⋮ Approximation of convex curves with application to the bicriterial minimum cost flow problem ⋮ The ellipsoid method and its implications ⋮ On the Length of Monotone Paths in Polyhedra ⋮ Efficient continuous-time dynamic network flow algorithms ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ Tight bounds on the number of minimum-mean cycle cancellations and related results ⋮ Unifying known lower bounds via geometric complexity theory ⋮ A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering ⋮ Algorithms for flows over time with scheduling costs

Cites Work