The Probabilistic Analysis of a Heuristic for the Assignment Problem

DOI10.1137/0217047MaRDI QIDQ3796776zbMATH OpenOpenAlexFDO

Authors

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0217047

zbMATH Keywords

assignment problemheuristicperfect matchingprobabilistic analysis of algorithmsweighted complete bipartite graphweighted matchings

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Average Case Analysis of a Heuristic for the Assignment Problem
• The random linear bottleneck assignment problem
• An analysis of a decomposition heuristic for the assignment problem
• The ``largest element first heuristic for the maximization assignment problem
• Constructive bounds and exact expectations for the random assignment problem

Cited in

(20)

• An analysis of a decomposition heuristic for the assignment problem
• The ``largest element first heuristic for the maximization assignment problem
• Probabilistic analysis of the generalised assignment problem
• Heuristic and exact algorithms for the simultaneous assignment problem
• Probabilistic assignment: an extension approach
• The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
• On the probabilistic analysis of a decentralized version of one generalization of the assignment problem
• scientific article; zbMATH DE number 992001 (Why is no real title available?)
• Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck
• scientific article; zbMATH DE number 3932819 (Why is no real title available?)
• Average Case Analysis of a Heuristic for the Assignment Problem
• scientific article; zbMATH DE number 1031387 (Why is no real title available?)
• Optimality of belief propagation for random assignment problem
• Geometric algorithms for the minimum cost assignment problem
• A heuristic algorithm for the optimization of a retrial system with Bernoulli vacation
• A heuristic for the time constrained asymmetric linear sum assignment problem
• The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems
• A Probabilistic Approach to Solving Assignment Problems
• On optimality of a polynomial algorithm for random linear multidimensional assignment problem
• Random assignment problems

This page was built for publication: The Probabilistic Analysis of a Heuristic for the Assignment Problem

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