Average case performance of heuristics for multi-dimensional assignment problems

2010/04/23 by Alan Frieze, Frieze, Alan, Gregory B. Sorkin +2
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DM

paper · pdf · doi:10.48550/arxiv.1004.4239

arxiv created 2010/04/23 · openalex publication_date 2010/04/23 · arxiv updated 2010/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider multi-dimensional assignment problems in a probabilistic setting. Our main results are: (i) A new efficient algorithm for the 3-dimensional planar problem, based on enumerating and selecting from a set of "alternating-path trees"; (ii) A new efficient matching-based algorithm for the 3-dimensional axial problem.

Citations

• A Conjecture on random bipartite matching

Related

• Efficient algorithms for three-dimensional axial and planar random assignment problems
• Geometric versions of the 3-dimensional assignment problem under general norms
• Using stochastic order to compare different Euclidean Random Assignment Problems
• Online Multidimensional Packing Problems in the Random-Order Model
• The equivalence between two classic algorithms for the assignment problem