A strongly polynomial minimum cost circulation algorithm

DOI10.1007/BF02579369zbMATH Open0596.90030DBLPjournals/combinatorica/Tardos85WikidataQ56503920 ScholiaQ56503920MaRDI QIDQ1079110FDOQ1079110

Authors: Éva Tardos 

Publication date: 1985

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

strongly polynomialminimum cost circulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Cites Work

• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Factoring polynomials with rational coefficients
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Minimax Theorem for Directed Graphs
• A Primal-Dual Algorithm for Submodular Flows
• Monotone networks
• Systems of distinct representatives and linear algebra
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• Towards a Genuinely Polynomial Algorithm for Linear Programming

Cited In (only showing first 100 items - show all)

• Finding minimum-cost circulations by canceling negative cycles
• Complexity and algorithms for nonlinear optimization problems
• 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 fully combinatorial algorithm for submodular function minimization.
• Polyhedral Combinatorics in Combinatorial Optimization
• Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
• Minimum-cost flow algorithms: an experimental evaluation
• A dynamic programming algorithm for the \(k\)-haplotyping problem
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Title not available (Why is that?)
• Dual coordinate step methods for linear network flow problems
• Bilevel time minimizing assignment problem
• A faster polynomial algorithm for the constrained maximum flow problem
• Strong polynomial-time solvability of a minimum concave cost network flow problem.
• Inverse matroid intersection problem
• Inverse problem of minimum cuts
• A network penalty method
• 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\)
• 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
• Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm
• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• 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
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• An O (n ² (m + N log n )log n ) min-cost flow algorithm
• Campaign management under approval-driven voting rules
• An application of simultaneous diophantine approximation in combinatorial optimization
• A polynomial algorithm for b-matchings: An alternative approach
• A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
• Finding minimum-cost flows by double scaling
• On the computational behavior of a polynomial-time network flow algorithm
• Penelope's graph: a hard minimum cost tension instance
• An algorithm for fractional assignment problems
• Robust partial inverse network flow problems
• A strongly polynomial algorithm for the minimum cost tension problem
• Approximating and computing behavioural distances in probabilistic transition systems
• Bilevel time minimizing transportation problem
• 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
• Relaxation methods for monotropic programs
• Smoothed analysis of the successive shortest path algorithm
• Minimum-cost flows in unit-capacity networks
• Color constrained combinatorial optimization problems
• Minimum cost multiflows in undirected networks
• A least-squares minimum-cost network flow algorithm
• Note on Weintraub’s Minimum-Cost Circulation Algorithm
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• Shared processor scheduling of multiprocessor jobs
• An out-of-kilter method for the algebraic circulation problem
• About the minimum mean cycle-canceling algorithm
• A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
• An exterior simplex type algorithm for the minimum cost network flow problem
• Revisiting \(k\)-sum optimization
• 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
• Approximation algorithms for the maximum carpool matching problem
• Envy-free matchings with lower quotas
• A priority based assignment problem
• A gradient driven transportation algorithm
• A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
• Title not available (Why is that?)
• An alternate approach to solve two-level priority based assignment problem
• Substitution-based equipment balancing in service networks with multiple equipment types
• Title not available (Why is that?)
• A data-dependent approach for high-dimensional (robust) Wasserstein alignment
• Title not available (Why is that?)
• A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas
• A simple algorithm and min-max formula for the inverse arborescence problem
• Mathematical Considerations on the Relationship between the Ordering of players and Winning Probability in Certain Types of Team Sports
• Matchings under distance constraints. I
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• Dominated parasitic flow loops in networks
• Title not available (Why is that?)
• On circuit diameter bounds via circuit imbalances
• Geometric rescaling algorithms for submodular function minimization
• A primal-simplex based Tardos' algorithm
• Algorithmic meta-theorems for combinatorial reconfiguration revisited
• Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
• Algorithms and complexity analysis for some flow problems
• Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs
• Covering partially directed graphs with directed paths
• Flow logic
• Flow logic
• 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
• Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
• MAP inference algorithms without approximation for collective graphical models on path graphs via discrete difference of convex algorithm

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)