Finding minimum-cost circulations by canceling negative cycles

DOI10.1145/76359.76368zbMath0697.68063OpenAlexW2048790997WikidataQ56581179 ScholiaQ56581179MaRDI QIDQ3474897

Andrew V. Goldberg, Robert Endre Tarjan

Publication date: 1989

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/76359.76368

zbMATH Keywords

transportation problem network optimization network problems transshipment problem dynamic trees minimum-cost flow cycle cancelling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Related Items (64)

Evacuation planning by earliest arrival contraflow ⋮ Computing maximum mean cuts ⋮ Improved filtering for the bin-packing with cardinality constraint ⋮ Minimum cost multiflows in undirected networks ⋮ Approximation algorithms for solving the constrained arc routing problem in mixed graphs ⋮ Node-Balancing by Edge-Increments ⋮ Smoothed Analysis of the Successive Shortest Path Algorithm ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ A strongly polynomial algorithm for the minimum cost tension problem ⋮ A strongly polynomial contraction-expansion algorithm for network flow problems ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ On circuit diameter bounds via circuit imbalances ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Data locality and replica aware virtual cluster embeddings ⋮ Fractional 0-1 programming: applications and algorithms ⋮ Penelope's graph: a hard minimum cost tension instance ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Sparse PCA on fixed-rank matrices ⋮ The octatope abstract domain for verification of neural networks ⋮ Unnamed Item ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On solving maximum and quickest interval-valued flows over time ⋮ Linear fractional approximations for master problems in column generation ⋮ A minimum mean cycle cancelling method for nonlinear multicommodity flow problems ⋮ Finding minimum-cost flows by double scaling ⋮ About the minimum mean cycle-canceling algorithm ⋮ Polynomial-time primal simplex algorithms for the minimum cost network flow problem ⋮ A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices ⋮ A simple GAP-canceling algorithm for the generalized maximum flow problem ⋮ Algorithms for the minimum cost circulation problem based on maximizing the mean improvement ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ An algorithm to compute the nucleolus of shortest path games ⋮ Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks ⋮ A direct barter model for course add/drop process ⋮ Complexity analysis for maximum flow problems with arc reversals ⋮ A cycle augmentation algorithm for minimum cost multicommodity flows on a ring ⋮ Chips on wafers, or packing rectangles into grids ⋮ Maximum network flows with concave gains ⋮ Decomposition theorems for linear programs ⋮ A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks ⋮ Balanced-flow algorithm for path network planning in hierarchical spaces ⋮ Influence of the normalization constraint on the integral simplex using decomposition ⋮ Engineering Negative Cycle Canceling for Wind Farm Cabling ⋮ Profit maximization in flex-grid all-optical networks ⋮ Modular circulation and applications to traffic management ⋮ Vector Space Decomposition for Solving Large-Scale Linear Programs ⋮ A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time ⋮ On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows ⋮ Margin of victory for tournament solutions ⋮ Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité ⋮ Network Flow Optimization with Minimum Quantities ⋮ The minimum mean cycle-canceling algorithm for linear programs ⋮ Linking and cutting spanning trees ⋮ An integer programming approach for the Chinese postman problem with time-dependent travel time ⋮ Profit Maximization in Flex-Grid All-Optical Networks ⋮ Steiner Problems with Limited Number of Branching Nodes ⋮ Tight bounds on the number of minimum-mean cycle cancellations and related results ⋮ A new saling algorithm for the maximum mean cut problem ⋮ Approximate binary search algorithms for mean cuts and cycles

This page was built for publication: Finding minimum-cost circulations by canceling negative cycles