An efficient cost scaling algorithm for the assignment problem

DOI10.1007/BF01585996MaRDI QIDQ1914072zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM
• Faster Scaling Algorithms for Network Problems
• The assignment problem revisited
• scientific article; zbMATH DE number 1263274

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 53116 (Why is no real title available?)
• scientific article; zbMATH DE number 1263274 (Why is no real title available?)
• scientific article; zbMATH DE number 487935 (Why is no real title available?)
• scientific article; zbMATH DE number 515922 (Why is no real title available?)
• scientific article; zbMATH DE number 515923 (Why is no real title available?)
• scientific article; zbMATH DE number 515927 (Why is no real title available?)
• scientific article; zbMATH DE number 515928 (Why is no real title available?)
• scientific article; zbMATH DE number 515930 (Why is no real title available?)
• scientific article; zbMATH DE number 515937 (Why is no real title available?)
• scientific article; zbMATH DE number 515938 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• A new approach to the maximum-flow problem
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• Faster Scaling Algorithms for Network Problems
• Finding Minimum-Cost Circulations by Successive Approximation
• Global Price Updates Help
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• Improved Algorithms for Bipartite Network Flow
• Sublinear-Time Parallel Algorithms for Matching and Related Problems
• The auction algorithm: A distributed relaxation method for the assignment problem

Cited in

(25)

• Optimum matchings in weighted bipartite graphs
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• A new method for solving the assignment problem based on the permissible-edge algorithm for the minimum cost flow problem
• Multiscale edge detection using first-order derivative of anisotropic Gaussian kernels
• Towards auction algorithms for large dense assignment problems
• New scaling algorithms for the assignment and minimum mean cycle problems
• A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals
• Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs
• Enhanced lower bounds and exact procedures for total completion time minimization in a two‐machine permutation flowshop with release dates
• Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment
• Classes of linear programs solvable by coordinate-wise minimization
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• Reducing rank-maximal to maximum weight matching
• scientific article; zbMATH DE number 515928 (Why is no real title available?)
• On the role of distance transformations in Baddeley's delta metric
• Exact solution of emerging quadratic assignment problems
• The assignment problem revisited
• scientific article; zbMATH DE number 1787233 (Why is no real title available?)
• AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM
• Solving the rectangular assignment problem and applications
• A framework for edge detection based on relief functions
• Coarse graining of multiple water molecules with intelligent dissipative particle dynamics
• Linear assignment procedures
• The two-machine flowshop scheduling problem with sequence-independent setup times: new lower bounding strategies
• Algorithms and codes for dense assignment problems: The state of the art

Describes a project that uses

Uses Software

• DIMACS

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

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