Logo image
Back
Optimal Random Matchings on Trees and Applications
Conference proceeding   Peer reviewed

Optimal Random Matchings on Trees and Applications

Jeff Abrahamson, Bela Csaba and Ali Shokoufandeh
APPROXIMATION RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, PROCEEDINGS, v 5171, pp 254-265
01 Jan 2008
DOI: https://doi.org/10.1007/978-3-540-85363-3_21

Abstract

Computer Science Computer Science, Theory & Methods Mathematics Mathematics, Applied Physical Sciences Science & Technology Technology
In this paper we will consider tight upper and lower bounds on the weight of the optimal matching for random point sets distributed among the leaves of a tree, as a function of its cardinality. Specifically, given two n sets of points R = {r(1),..., r(n)} and B = {b(1),...,b(n)} distributed uniformly and randomly on the m leaves of lambda-Hierarchically Separated Trees with branching factor b such that each of its leaves is at depth delta, we will prove that the expected weight of optimal matching between R and B is Theta(root nb Sigma(h)(kappa=1) (root b lambda)(kappa)), for h = min(delta, log(b) n). Using a simple embedding algorithm from R-d to HSTs, we are able to reproduce the results concerning the expected optimal transportation cost in [0, 1](d), except for d = 2. We also show that giving random weights to the points does not affect the expected matching weight by more than a constant factor. Finally, we prove upper bounds on several sets for which showing reasonable matching results would previously have been intractable, e.g., the Cantor set, and various fractals.

Metrics

10 Record Views
1 citations in Web of Science
1 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
Web of Science research areas
Computer Science, Theory & Methods
Mathematics, Applied
Logo image