On the Expected Value of a Random Assignment Problem

DOI10.1137/0208036zbMath0413.68062OpenAlexW2003351966MaRDI QIDQ3048272

David W. Walkup

Publication date: 1979

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

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

zbMATH Keywords

sparse graphsminimum weight matchingrandom assignment problemaverage value

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)

Related Items (38)

The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach ⋮ On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees ⋮ Order statistics and the linear assignment problem ⋮ On linear programs with random costs ⋮ Minimean optimal key arrangements in hash tables ⋮ Maximal paths in random dynamic graphs ⋮ Concentration of measure and isoperimetric inequalities in product spaces ⋮ On the longest path of a randomly weighted tournament ⋮ Asymptotic behavior of the expected optimal value of the multidimensional assignment problem ⋮ The mean field traveling salesman and related problems ⋮ The random linear bottleneck assignment problem ⋮ Matchings in random regular bipartite digraphs ⋮ Probabilistic analysis of optimization problems on sparse random shortest path metrics ⋮ The planted matching problem: sharp threshold and infinite-order phase transition ⋮ Minimum Cost Matching in a Random Graph with Random Costs ⋮ Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations ⋮ On randomk-out subgraphs of large graphs ⋮ One-factor in random graphs based on vertex choice ⋮ Minimum-weight combinatorial structures under random cost-constraints ⋮ Exploiting partial correlations in distributionally robust optimization ⋮ The ?(2) limit in the random assignment problem ⋮ Random assignment problems ⋮ Asymptotics in the random assignment problem ⋮ Selected topics on assignment problems ⋮ A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment ⋮ Uncertain programming model for uncertain optimal assignment problem ⋮ Uncertain random assignment problem ⋮ Constructive bounds and exact expectations for the random assignment problem ⋮ The planted matching problem: phase transitions and exact results ⋮ The Effect of Adding Randomly Weighted Edges ⋮ The minimum perfect matching in pseudo-dimension 0 < q < 1 ⋮ The asymptotic probabilistic behaviour of quadratic sum assignment problems ⋮ On the connectivity of random m-orientable graphs and digraphs ⋮ An analysis of a decomposition heuristic for the assignment problem ⋮ On the value of a random minimum spanning tree problem ⋮ On the expected optimal value of random assignment problems: Experimental results and open questions ⋮ Probabilistic asymptotic properties of some combinatorial optimization problems ⋮ Asymptotic results for random multidimensional assignment problems

This page was built for publication: On the Expected Value of a Random Assignment Problem