Metric random matchings with applications

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({\boldsymbol{\pi}}(2i-1),{\boldsymbol{\pi}}(2i))$ for a uniformly random permutation $\mathit{\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+ϵ)$-approximate solution in expected $O(n\mathrm{/}{ϵ}^2)$ time and that (2) inherits Indyk’s~\cite{Ind99, Ind00} algorithm to output a $(1+ϵ)$-approximate solution in $O(n\mathrm{/}{ϵ}^2)$ time with probability $\mathrm{\Omega }(1)$, where $ϵ\in (0,1)$. (II) The average distance in $(\{1,2,\dots ,n\},d)$ can be approximated in $O(n\mathrm{/}ϵ)$ time to within a multiplicative factor in $[1\mathrm{/}2-ϵ,1]$ with probability $1\mathrm{/}2+\mathrm{\Omega }(1)$, where $ϵ>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-ϵ,1+ϵ]$ with probability $1\mathrm{/}2+\mathrm{\Omega }(1)$, where $ϵ=\omega (1\mathrm{/}{n}^{1\mathrm{/}4})$.