An efficient cost scaling algorithm for the assignment problem

DOI10.1007/BF01585996zbMath0846.90118OpenAlexW1981020230MaRDI QIDQ1914072

Yanyan Li

Publication date: 3 October 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585996

zbMATH Keywords

assignment problemexperimental evaluationcost scalingcost scaling push-related methodminimum-cost flow problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (18)

Optimum matchings in weighted bipartite graphs ⋮ The assignment problem revisited ⋮ Towards auction algorithms for large dense assignment problems ⋮ Classes of linear programs solvable by coordinate-wise minimization ⋮ Enhanced lower bounds and exact procedures for total completion time minimization in a two‐machine permutation flowshop with release dates ⋮ On the role of distance transformations in Baddeley's delta metric ⋮ Solving the rectangular assignment problem and applications ⋮ Algorithms and codes for dense assignment problems: The state of the art ⋮ Exact solution of emerging quadratic assignment problems ⋮ Reducing rank-maximal to maximum weight matching ⋮ A framework for edge detection based on relief functions ⋮ A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals ⋮ Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment ⋮ Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs ⋮ Multiscale edge detection using first-order derivative of anisotropic Gaussian kernels ⋮ Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order ⋮ Linear assignment procedures ⋮ The two-machine flowshop scheduling problem with sequence-independent setup times: new lower bounding strategies

Uses Software

• DIMACS

Cites Work

• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• The auction algorithm: A distributed relaxation method for the assignment problem
• Finding Minimum-Cost Circulations by Successive Approximation
• A new approach to the maximum-flow problem
• Sublinear-Time Parallel Algorithms for Matching and Related Problems
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• Improved Algorithms for Bipartite Network Flow
• Global Price Updates Help
• Faster Scaling Algorithms for Network Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An efficient cost scaling algorithm for the assignment problem