A strongly polynomial minimum cost circulation algorithm

Recommendations

scientific article; zbMATH DE number 3900474
A Faster Strongly Polynomial Minimum Cost Flow Algorithm
A strongly polynomial algorithm for the minimum cost tension problem
An O (n ² (m + N log n )log n ) min-cost flow algorithm
A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

Cites work

scientific article; zbMATH DE number 3174052 (Why is no real title available?)
scientific article; zbMATH DE number 3580570 (Why is no real title available?)
scientific article; zbMATH DE number 3349645 (Why is no real title available?)
A Minimax Theorem for Directed Graphs
A Primal-Dual Algorithm for Submodular Flows
An Out-of-Kilter Method for Minimal-Cost Flow Problems
Factoring polynomials with rational coefficients
Monotone networks
Systems of distinct representatives and linear algebra
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Towards a Genuinely Polynomial Algorithm for Linear Programming

Cited in

(only showing first 100 items - show all)

An exterior simplex type algorithm for the minimum cost network flow problem
Flow games
A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
Revisiting k-sum optimization
Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
A new strongly polynomial dual network simplex algorithm
George Dantzig's impact on the theory of computation
The auction algorithm: A distributed relaxation method for the assignment problem
Tight bounds on the number of minimum-mean cycle cancellations and related results
The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications
Decreasing minimization on M-convex sets: algorithms and applications
Random walks on the vertices of transportation polytopes with constant number of sources
Approximation algorithms for the maximum carpool matching problem
Envy-free matchings with lower quotas
Finding minimum-cost circulations by canceling negative cycles
Complexity and algorithms for nonlinear optimization problems
A priority based assignment problem
Min-Cost Flow in Unit-Capacity Planar Graphs
The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
A gradient driven transportation algorithm
A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
A fully combinatorial algorithm for submodular function minimization.
Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
scientific article; zbMATH DE number 447202 (Why is no real title available?)
An alternate approach to solve two-level priority based assignment problem
Substitution-based equipment balancing in service networks with multiple equipment types
Minimum-cost flow algorithms: an experimental evaluation
Polyhedral Combinatorics in Combinatorial Optimization
A dynamic programming algorithm for the \(k\)-haplotyping problem
Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
scientific article; zbMATH DE number 4057295 (Why is no real title available?)
A data-dependent approach for high-dimensional (robust) Wasserstein alignment
scientific article; zbMATH DE number 7559206 (Why is no real title available?)
Dual coordinate step methods for linear network flow problems
scientific article; zbMATH DE number 3900474 (Why is no real title available?)
A simple algorithm and min-max formula for the inverse arborescence problem
A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas
Bilevel time minimizing assignment problem
A faster polynomial algorithm for the constrained maximum flow problem
Inverse matroid intersection problem
Strong polynomial-time solvability of a minimum concave cost network flow problem.
A network penalty method
Inverse problem of minimum cuts
Matchings under distance constraints. I
Mathematical Considerations on the Relationship between the Ordering of players and Winning Probability in Certain Types of Team Sports
A polynomial time primal network simplex algorithm for minimum cost flows
Approximation algorithms for solving the constrained arc routing problem in mixed graphs
A dual version of Tardos's algorithm for linear programming
A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
New scaling algorithms for the assignment and minimum mean cycle problems
The minimal average cost flow problem
Two level hierarchical time minimizing transportation problem
A double scaling algorithm for the constrained maximum flow problem
Subspaces with well-scaled frames
Dominated parasitic flow loops in networks
Minimum vertex weighted deficiency of (g,f)-factors: A greedy algorithm
Two strongly polynomial cut cancelling algorithms for minimum cost network flow
scientific article; zbMATH DE number 7278072 (Why is no real title available?)
On the maximum capacity augmentation algorithm for the maximum flow problem
A strongly polynomial algorithm for generalized flow maximization
A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers
Campaign management under approval-driven voting rules
Geometric rescaling algorithms for submodular function minimization
On circuit diameter bounds via circuit imbalances
An application of simultaneous diophantine approximation in combinatorial optimization
A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
A polynomial algorithm for b-matchings: An alternative approach
An O (n ² (m + N log n )log n ) min-cost flow algorithm
Finding minimum-cost flows by double scaling
A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
A primal-simplex based Tardos' algorithm
On the computational behavior of a polynomial-time network flow algorithm
Penelope's graph: a hard minimum cost tension instance
Algorithms and complexity analysis for some flow problems
Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs
An algorithm for fractional assignment problems
Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
Algorithmic meta-theorems for combinatorial reconfiguration revisited
A strongly polynomial algorithm for the minimum cost tension problem
Covering partially directed graphs with directed paths
Robust partial inverse network flow problems
Approximating and computing behavioural distances in probabilistic transition systems
Bilevel time minimizing transportation problem
Flow logic
Flow logic
A polynomial dual simplex algorithm fot the generalized circulation problem.
Inverse problems of submodular functions on digraphs
Minimizing the number of tardy job units under release time constraints
An update-and-stabilize framework for the minimum-norm-point problem
Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
Relaxation methods for monotropic programs
Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
Color constrained combinatorial optimization problems
Minimum-cost flows in unit-capacity networks
A least-squares minimum-cost network flow algorithm
Minimum cost multiflows in undirected networks
Smoothed analysis of the successive shortest path algorithm
Polynomial-time primal simplex algorithms for the minimum cost network flow problem
Data locality and replica aware virtual cluster embeddings

This page was built for publication: A strongly polynomial minimum cost circulation algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079110)