On the number of k-cycles in the assignment problem for random matrices

DOI10.1088/1742-5468/2008/03/P03019MaRDI QIDQ5239474zbMATH OpenOpenAlexFDO

Authors Fernando Falceto, J. G. Esteve

Publication date 22 October 2019

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1088/1742-5468/2008/03/p03019

zbMATH Keywords

networksrandom graphstypical-case computational complexity

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31)

Recommendations

• On the expected number of assignments in reduced matrices for the linear assignment problem
• scientific article; zbMATH DE number 1802784
• Certain expected values in the random assignment problem
• The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

Cites work

• scientific article; zbMATH DE number 3679828 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• A proof of Parisi's conjecture on the random assignment problem
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• Exact solution of the random bipartite matching model
• Matching theory
• On Random Symmetric Travelling Salesman Problems
• The Traveling Salesman Problem with Distances One and Two
• The (2) limit in the random assignment problem
• The probabilistic relationship between the assignment and asymmetric traveling salesman problems.

Cited in

(1)

• On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns

This page was built for publication: On the number of \(k\)-cycles in the assignment problem for random matrices

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