2010/08/02 by Alan Frieze, Frieze, Alan, Gregory B. Sorkin +2
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Packing Problems #Optimization and Search Problems #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1008.0390
openalex publication_date 2010/08/02 · arxiv created 2013/10/08 · arxiv updated 2013/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Beautiful formulas are known for the expected cost of random two-dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural "Axial" and "Planar" versions, both of which are NP-hard. For 3-dimensional Axial random assignment instances of size n, the cost scales as Ω(1/n), and a main result of the present paper is a linear-time algorithm that, with high probability, finds a solution of cost O(n-1+o(1)). For 3-dimensional Planar assignment, the lower bound is Ω(n), and we give a new efficient matching-based algorithm that with high probability returns a solution with cost O(n log n).