Finding minimum-cost circulations by canceling negative cycles

DOI10.1145/76359.76368zbMATH Open0697.68063DBLPjournals/jacm/GoldbergT89OpenAlexW2048790997WikidataQ56581179 ScholiaQ56581179MaRDI QIDQ3474897FDOQ3474897

Authors: Andrew V. Goldberg, Robert E. 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

Recommendations

• Finding Minimum-Cost Circulations by Successive Approximation
• New polynomial-time cycle-canceling algorithms for minimum-cost flows
• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• scientific article; zbMATH DE number 3900474
• A strongly polynomial minimum cost circulation algorithm

zbMATH Keywords

transportation problemnetwork optimizationnetwork problemstransshipment problemdynamic treesminimum-cost flowcycle 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)

Cited In (74)

• Steiner problems with limited number of branching nodes
• Linear fractional approximations for master problems in column generation
• A direct barter model for course add/drop process
• On circuit diameter bounds via circuit imbalances
• Linking and cutting spanning trees
• Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité
• Evacuation planning by earliest arrival contraflow
• An algorithm to compute the nucleolus of shortest path games
• Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
• Minimum-cost flow algorithms: an experimental evaluation
• Chips on wafers, or packing rectangles into grids
• Improved filtering for the bin-packing with cardinality constraint
• Fractional 0-1 programming: applications and algorithms
• Maximum contraflow evacuation planning problems on multi-network
• Complexity analysis for maximum flow problems with arc reversals
• A cycle augmentation algorithm for minimum cost multicommodity flows on a ring
• Approximation algorithms for solving the constrained arc routing problem in mixed graphs
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
• Influence of the normalization constraint on the integral simplex using decomposition
• Network flow optimization with minimum quantities
• Profit maximization in flex-grid all-optical networks
• Vector Space Decomposition for Solving Large-Scale Linear Programs
• A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks
• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• A strongly polynomial algorithm for generalized flow maximization
• On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows
• A strongly polynomial contraction-expansion algorithm for network flow problems
• The minimum mean cycle-canceling algorithm for linear programs
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• Finding minimum-cost flows by double scaling
• Penelope's graph: a hard minimum cost tension instance
• Title not available (Why is that?)
• Approximate binary search algorithms for mean cuts and cycles
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• A strongly polynomial algorithm for the minimum cost tension problem
• Maximum network flows with concave gains
• Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
• Balanced-flow algorithm for path network planning in hierarchical spaces
• Margin of victory for tournament solutions
• Decomposition theorems for linear programs
• Smoothed analysis of the successive shortest path algorithm
• Minimum cost multiflows in undirected networks
• Data locality and replica aware virtual cluster embeddings
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• About the minimum mean cycle-canceling algorithm
• A new saling algorithm for the maximum mean cut problem
• Profit maximization in flex-grid all-optical networks
• The octatope abstract domain for verification of neural networks
• An integer programming approach for the Chinese postman problem with time-dependent travel time
• A minimum mean cycle cancelling method for nonlinear multicommodity flow problems
• Computing maximum mean cuts
• Sparse PCA on fixed-rank matrices
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• A combinatorial cut-toggling algorithm for solving Laplacian linear systems
• Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow
• Multicommodity network flows: A survey. II: Solution methods
• A simple GAP-canceling algorithm for the generalized maximum flow problem
• A data-dependent approach for high-dimensional (robust) Wasserstein alignment
• A bicriteria almost equal minimum cost flow model for day-ahead trading
• Dominated parasitic flow loops in networks
• On circuit diameter bounds via circuit imbalances
• Minimal number of periodic orbits for non-singular Morse-Smale flows in odd dimension
• Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
• Dynamic network contraflow evacuation planning problem with continuous time approach
• Modular circulation and applications to traffic management
• Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
• On solving maximum and quickest interval-valued flows over time
• Node-balancing by edge-increments
• A strongly polynomial algorithm for approximate Forster transforms and its application to halfspace learning
• The hexatope and octatope abstract domains for neural network verification
• Engineering Negative Cycle Canceling for Wind Farm Cabling
• Belief propagation for unbalanced assignment problem

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

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