A Faster Strongly Polynomial Minimum Cost Flow Algorithm
From MaRDI portal
Publication:5288156
DOI10.1287/opre.41.2.338zbMath0781.90036OpenAlexW2156036190MaRDI QIDQ5288156
Publication date: 9 August 1993
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/2206
shortest pathscalingminimum cost flowstrongly polynomial time algorithmuncapacitated minimum cost flow
Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)
Related Items
A solution technique for capacitated two-level hierarchical time minimization transportation problem, Fast upper and lower bounds for a large‐scale real‐world arc routing problem, The single robot line coverage problem: Theory, algorithms, and experiments, Approximation algorithms for solving the constrained arc routing problem in mixed graphs, The mixed evacuation problem, A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem, Inverse obnoxious \(p\)-median location problems on trees with edge length modifications under different norms, Recent developments in maximum flow algorithms, A 3/2-Approximation for the Metric Many-Visits Path TSP, 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, Separation, dimension, and facet algorithms for node flow polyhedra, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm, The assignment problem with nearly Monge arrays and incompatible partner indices, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm, Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, On the complexity of energy storage problems, A polynomial time primal network simplex algorithm for minimum cost flows, A new strongly polynomial dual network simplex algorithm, A novel approach to subgraph selection with multiple weights on arcs, Finding all minimum cost flows and a faster algorithm for the \(K\) best flow problem, Power optimization for connectivity problems, Two-stage matching-and-scheduling algorithm for real-time private parking-sharing programs, Multiindex transportation problems with 2-embedded structure, Minimum-cost flow algorithms: an experimental evaluation, Profile-Based Optimal Matchings in the Student/Project Allocation Problem, Exact and approximation algorithms for the operational fixed interval scheduling problem, A combinatorial algorithm for the 1-median problem in \(\mathbb R^d\) with the Chebyshev norm, Transportation distances on the circle, A fast maximum flow algorithm, An update-and-stabilize framework for the minimum-norm-point problem, Optimizing time–cost trade-off decisions in an interval transportation problem with multiple shipment options, Flow constrained minimum cost flow problem, Finding optimal non-datapath caching strategies via network flow, The Mixed Evacuation Problem, Algorithmic Aspects of Disjunctive Total Domination in Graphs, An \(O(n(m+n\log n)\log n)\) time algorithm to solve the minimum cost tension problem, The battery switching station scheduling problem, Minimum-cost flows in unit-capacity networks, A survey on exact algorithms for the maximum flow and minimum‐cost flow problems, Finding total unimodularity in optimization problems solved by linear programs, A linear optimal transportation framework for quantifying and visualizing variations in sets of images, An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem, A Strongly Polynomial Algorithm for Generalized Flow Maximization, A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas, Unnamed Item, Algorithms for distributing telecommunication traffic on a multiple-ring SONET-based network., A least-squares minimum-cost network flow algorithm, Updating network flows given multiple, heterogeneous arc attribute changes, Complexity of strict robust integer minimum cost flow problems: an overview and further results, A new scaling algorithm for the minimum cost network flow problem, Monotonizing linear programs with up to two nonzeroes per column, Network flow with intermediate storage: models and algorithms, Bi-criteria transportation problem with multiple parameters, Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, From stars to comets: improved local search for universal facility location, Many Visits TSP Revisited, Modifying orthogonal drawings for label placement, Allocation under a general substitution structure, Exterior point simplex-type algorithms for linear and network optimization problems, Matching point sets with respect to the earth mover's distance, A NEW APPROACH FOR SOLVING THE MINIMUM COST FLOW PROBLEM WITH INTERVAL AND FUZZY DATA, Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks, A polynomial algorithm for a two-stage time minimizing transportation problem., Envy-free matchings with lower quotas, Finding coherent cyclic orders in strong digraphs, On the optimum capacity of capacity expansion problems, A network simplex method for the budget-constrained minimum cost flow problem, An exterior simplex type algorithm for the minimum cost network flow problem, A heuristic method for solving integer-valued decompositional multiindex problems, Minimal multicut and maximal integer multiflow: a survey, On the Pythagorean Structure of the Optimal Transport for Separable Cost Functions, The problem of synthesis of reliable networks, Unnamed Item, Shared processor scheduling of multiprocessor jobs, Empirical optimal transport on countable metric spaces: distributional limits and statistical applications, The blocking job shop with rail-bound transportation, A faster polynomial algorithm for the unbalanced Hitchcock transportation problem, Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width, Better bounds for minimizing SONET ADMs, Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with monge costs, Fast algorithms for convex cost flow problems on circles, lines, and trees, A minimum cost flow formulation for approximated MLC segmentation, Approximation Algorithms for the Single Robot Line Coverage Problem, A unified framework for clustering constrained data without locality property, Multimode resource-constrained project scheduling in flexible projects, Many-visits TSP revisited, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, Geometric quadrisection in linear time, with application to VLSI placement, On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows, Complexity, algorithms and applications of the integer network flow with fractional supplies problem, The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs, Network Flow Optimization with Minimum Quantities, Unnamed Item, Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models, A New Approach to the Pareto Stable Matching Problem, Discrete Newton methods for the evacuation problem, Problems of synthesis of connected networks with respect to isomorphic subgraphs, Efficient Large-Scale Multi-Drone Delivery using Transit Networks, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, A greedy algorithm for multicut and integral multiflow in rooted trees, A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
