Finding Minimum-Cost Circulations by Successive Approximation
From MaRDI portal
Publication:3351112
DOI10.1287/moor.15.3.430zbMath0727.90024OpenAlexW2061872629WikidataQ29306097 ScholiaQ29306097MaRDI QIDQ3351112
Andrew V. Goldberg, Robert Endre Tarjan
Publication date: 1990
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.15.3.430
successive approximationsymmetric digraphcost scaling proceduresminimum cost circulation problemspseudoflows
Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Data parallel computing for network-structured optimization problems, Fair matchings and related problems, A decomposition approach for a resource constrained scheduling problem, Efficient contraflow algorithms for quickest evacuation planning, Improving time bounds on maximum generalised flow computations by contracting the network, Truthful mechanism design for multidimensional scheduling via cycle monotonicity, A fast cost scaling algorithm for submodular flow, A decomposition approach in a DSS for a resource constrained scheduling problem, The assignment problem revisited, Recent developments in maximum flow algorithms, A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows, Smoothed Analysis of the Successive Shortest Path Algorithm, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Separation, dimension, and facet algorithms for node flow polyhedra, A sparse multiscale algorithm for dense optimal transport, Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time, An efficient cost scaling algorithm for the assignment problem, A polynomial time primal network simplex algorithm for minimum cost flows, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, How to compute least infeasible flows, Efficient parallel algorithms for the minimum cost flow problem, A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks, A faster strongly polynomial time algorithm to solve the minimum cost tension problem, A Simple Efficient Interior Point Method for Min-Cost Flow, Minimum-cost flow algorithms: an experimental evaluation, Computing Minimum Length Representations of Sets of Words of Uniform Length, Minimum cost noncrossing flow problem on layered networks, Characterization of random walks on space of unordered trees using efficient metric simulation, Maximum skew-symmetric flows, SIRALINA: Efficient two-steps heuristic for storage optimisation in single period task scheduling, Finding optimal non-datapath caching strategies via network flow, An \(O(n(m+n\log n)\log n)\) time algorithm to solve the minimum cost tension problem, Minimum-cost flows in unit-capacity networks, Conflict-tolerant and conflict-free multi-agent meeting, A survey on exact algorithms for the maximum flow and minimum‐cost flow problems, Approximation algorithms for \(k\)-hurdle problems, The balanced \(p\)-median problem with unitary demand, Simplified linear-time Jordan sorting and polygon clipping, An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem, Unnamed Item, Unnamed Item, Algorithms and codes for dense assignment problems: The state of the art, On the transformation mechanism for formulating a multiproduct two-layer supply chain network design problem as a network flow model, A new scaling algorithm for the minimum cost network flow problem, A sparse algorithm for dense optimal transport, Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems, Finding minimum-cost flows by double scaling, A double scaling algorithm for the constrained maximum flow problem, On the computational behavior of a polynomial-time network flow algorithm, Polynomial-time primal simplex algorithms for the minimum cost network flow problem, A new fixed point approach for stable networks and stable marriages, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Auction algorithms for network flow problems: A tutorial introduction, Using combinatorial optimization in model-based trimmed clustering with cardinality constraints, A faster polynomial algorithm for the constrained maximum flow problem, Online hole healing for sensor coverage, A combinatorial approximation algorithm for concurrent flow problem and its application, A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows, The problem of synthesis of reliable networks, A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks, Multicommodity flows in tree-like networks, A faster polynomial algorithm for the unbalanced Hitchcock transportation problem, Approximation Algorithms for k-Hurdle Problems, Min-Cost Flow in Unit-Capacity Planar Graphs, A parallel algorithm for finding a blocking flow in an acyclic network, Implementation and test of auction methods for solving generalized network flow problems with separable convex cost, Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems, Algorithms for network piecewise-linear programs: A comparative study, Efficient algorithms for abstract flow with partial switching, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, A generic auction algorithm for the minimum cost network flow problem, Tight bounds on the number of minimum-mean cycle cancellations and related results, Network flow and 2-satisfiability, On the complexity of preflow-push algorithms for maximum-flow problems, Computing minimum length representations of sets of words of uniform length
