A Simple Efficient Interior Point Method for Min-Cost Flow

DOI10.1007/978-3-319-13075-0_59MaRDI QIDQ2942676zbMATH OpenOpenAlexFDO

Authors Ruben Becker, Andreas Karrenbauer

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-13075-0_59

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic network models in operations research (90B10) Interior-point methods (90C51)

Recommendations

• A POLYNOMIAL TIME INTERIOR POINT ALGORITHM FOR MINIMUM COST FLOW PROBLEMS
• INTERIOR METHODS FOR NONLINEAR MINIMUM COST NETWORK FLOW PROBLEMS
• A combinatorial interior point method for network flow problems
• Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs
• scientific article; zbMATH DE number 515933
• scientific article; zbMATH DE number 1263274
• A POLYNOMIAL-TIME DUAL SIMPLEX ALGORITHM FOR THE MINIMUM COST FLOW PROBLEM
• A dual exterior point simplex type algorithm for the minimum cost network flow problem
• A network simplex method for the budget-constrained minimum cost flow problem
• An exterior simplex type algorithm for the minimum cost network flow problem

Cites work

• scientific article; zbMATH DE number 5485557 (Why is no real title available?)
• scientific article; zbMATH DE number 3393943 (Why is no real title available?)
• A new polynomial-time algorithm for linear programming
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Approaching optimality for solving SDD linear systems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Finding Minimum-Cost Circulations by Successive Approximation
• Finding minimum-cost flows by double scaling
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Network flows. Theory, algorithms, and applications.
• Using petal-decompositions to build a low stretch spanning tree

Cited in

(1)

• A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks

This page was built for publication: A Simple Efficient Interior Point Method for Min-Cost Flow

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