Inexpensive d‐dimensional matchings |
| |
Authors: | Bae‐Shi Huang Ljubomir Perkovi Eric Schmutz |
| |
Institution: | Bae‐Shi Huang,Ljubomir Perković,Eric Schmutz |
| |
Abstract: | Suppose that independent U(0, 1) weights are assigned to the ${d\choose 2}n^{2}$ 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 $\frac{3}{16}n^{1-(2/d)}$. We describe a randomized algorithm that finds a perfect d‐dimensional matching whose expected weight is at most 5d3n1?(2/d)+d15 for all d≥3 and n≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002 |
| |
Keywords: | |
|
|