Inexpensive d ‐dimensional matchings

Suppose that independent U (0, 1) weights are assigned to the \documentclass{article}\pagestyle{empty}\begin{document}${d\choose 2}n^{2}$\end{document} edges of the complete d ‐partite graph with n vertices in each of the d maximal independent sets. Then the expected weight of the minimum‐weight perfect d ‐dimensional matching is at least \documentclass{article}\pagestyle{empty}\begin{document}$\frac{3}{16}n^{1-(2/d)}$\end{document} . We describe a randomized algorithm that finds a perfect d ‐dimensional matching whose expected weight is at most 5 d 3 n 1−(2/ d ) + d 15 for all d ≥3 and n ≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002