Metric random matchings with applications

Abstract

Let $(\{1,2,\dots ,n\},d)$ be a metric space. We analyze the expected value and the variance of ${\sum }_{i=1}^{\lfloor n/2\rfloor }d(\mathbf{\pi }(2i-1),\mathbf{\pi }(2i))$ for a uniformly random permutation $\mathbf{\pi }$ of $\{1,2,\dots ,n\}$, leading to the following results: (I) Consider the problem of finding a point in $\{1,2,\dots ,n\}$ with the minimum sum of distances to all points. We show that this problem has a randomized algorithm that (1) always outputs a $(2+\epsilon )$-approximate solution in expected $O(n/{\epsilon }^2)$ time and that (2) inherits Indyk's~\cite{Ind99, Ind00} algorithm to output a $(1+\epsilon )$-approximate solution in $O(n/{\epsilon }^2)$ time with probability $\Omega (1)$, where $\epsilon \in (0,1)$. (II) The average distance in $(\{1,2,\dots ,n\},d)$ can be approximated in $O(n/\epsilon )$ time to within a multiplicative factor in $[1/2-\epsilon ,1]$ with probability $1/2+\Omega (1)$, where $\epsilon >0$. (III) Assume $d$ to be a graph metric. Then the average distance in $(\{1,2,\dots ,n\},d)$ can be approximated in $O(n)$ time to within a multiplicative factor in $[1-\epsilon ,1+\epsilon ]$ with probability $1/2+\Omega (1)$, where $\epsilon =\omega (1/n^{1/4})$.

arXiv admin note: substantial text overlap with arXiv:1702.03106