A strongly polynomial minimum cost circulation algorithm
From MaRDI portal
Publication:1079110
DOI10.1007/BF02579369zbMath0596.90030WikidataQ56503920 ScholiaQ56503920MaRDI QIDQ1079110
Publication date: 1985
Published in: Combinatorica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)
Related Items
A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks ⋮ Minimum cost multiflows in undirected networks ⋮ A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers ⋮ Approximation algorithms for solving the constrained arc routing problem in mixed graphs ⋮ Smoothed Analysis of the Successive Shortest Path Algorithm ⋮ Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization ⋮ An application of simultaneous diophantine approximation in combinatorial optimization ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ A strongly polynomial algorithm for the minimum cost tension problem ⋮ Inverse matroid intersection problem ⋮ A polynomial algorithm for b-matchings: An alternative approach ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ Bilevel time minimizing assignment problem ⋮ Dual coordinate step methods for linear network flow problems ⋮ Approximation algorithms for the maximum carpool matching problem ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ A new strongly polynomial dual network simplex algorithm ⋮ Unnamed Item ⋮ A gradient driven transportation algorithm ⋮ A simple algorithm and min-max formula for the inverse arborescence problem ⋮ A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables ⋮ Subspaces with well-scaled frames ⋮ A strongly polynomial algorithm for a new class of linear inequalities1 ⋮ Data locality and replica aware virtual cluster embeddings ⋮ Revisiting \(k\)-sum optimization ⋮ Penelope's graph: a hard minimum cost tension instance ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ The minimal average cost flow problem ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ Polyhedral Combinatorics in Combinatorial Optimization ⋮ An update-and-stabilize framework for the minimum-norm-point problem ⋮ MAP inference algorithms without approximation for collective graphical models on path graphs via discrete difference of convex algorithm ⋮ Minimum-cost flows in unit-capacity networks ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Unnamed Item ⋮ Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks ⋮ A dynamic programming algorithm for the \(k\)-haplotyping problem ⋮ Relaxation methods for monotropic programs ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas ⋮ Unnamed Item ⋮ A least-squares minimum-cost network flow algorithm ⋮ Minimizing the number of tardy job units under release time constraints ⋮ A network penalty method ⋮ A new scaling algorithm for the minimum cost network flow problem ⋮ Color constrained combinatorial optimization problems ⋮ Finding minimum-cost flows by double scaling ⋮ A double scaling algorithm for the constrained maximum flow problem ⋮ About the minimum mean cycle-canceling algorithm ⋮ On the computational behavior of a polynomial-time network flow algorithm ⋮ New scaling algorithms for the assignment and minimum mean cycle problems ⋮ Envy-free matchings with lower quotas ⋮ Matchings under distance constraints. I ⋮ The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications ⋮ Polynomial-time primal simplex algorithms for the minimum cost network flow problem ⋮ George Dantzig's impact on the theory of computation ⋮ Campaign management under approval-driven voting rules ⋮ Bilevel time minimizing transportation problem ⋮ Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm ⋮ An exterior simplex type algorithm for the minimum cost network flow problem ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ A faster polynomial algorithm for the constrained maximum flow problem ⋮ Two level hierarchical time minimizing transportation problem ⋮ Robust partial inverse network flow problems ⋮ Covering partially directed graphs with directed paths ⋮ Unnamed Item ⋮ A dual version of Tardos's algorithm for linear programming ⋮ Approximating and computing behavioural distances in probabilistic transition systems ⋮ A min-max relation for stable sets in graphs with no odd-\(K_ 4\) ⋮ A primal-simplex based Tardos' algorithm ⋮ Random walks on the vertices of transportation polytopes with constant number of sources ⋮ Shared processor scheduling of multiprocessor jobs ⋮ Geometric Rescaling Algorithms for Submodular Function Minimization ⋮ A priority based assignment problem ⋮ Unnamed Item ⋮ The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs ⋮ Min-Cost Flow in Unit-Capacity Planar Graphs ⋮ A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Inverse problems of submodular functions on digraphs ⋮ An algorithm for fractional assignment problems ⋮ Inverse problem of minimum cuts ⋮ Decreasing minimization on M-convex sets: algorithms and applications ⋮ A fully combinatorial algorithm for submodular function minimization. ⋮ On the maximum capacity augmentation algorithm for the maximum flow problem ⋮ Tight bounds on the number of minimum-mean cycle cancellations and related results ⋮ Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs ⋮ Algorithms and complexity analysis for some flow problems ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix ⋮ The auction algorithm: A distributed relaxation method for the assignment problem ⋮ An alternate approach to solve two-level priority based assignment problem ⋮ Substitution-based equipment balancing in service networks with multiple equipment types
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Factoring polynomials with rational coefficients
- Monotone networks
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- A Primal-Dual Algorithm for Submodular Flows
- An Out-of-Kilter Method for Minimal-Cost Flow Problems
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- A Minimax Theorem for Directed Graphs
- Systems of distinct representatives and linear algebra
