Noisy Sorting Without Resampling - Computer Science > Data Structures and AlgorithmsReport as inadecuate

Noisy Sorting Without Resampling - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: In this paper we study noisy sorting without re-sampling. In this problemthere is an unknown order $a {\pi1} <

. < a {\pin}$ where $\pi$ is apermutation on $n$ elements. The input is the status of $n \choose 2$ queriesof the form $qa i,x j$, where $qa i,a j = +$ with probability at least$1-2+\ga$ if $\pii > \pij$ for all pairs $i eq j$, where $\ga > 0$ is aconstant and $qa i,a j = -qa j,a i$ for all $i$ and $j$. It is assumed thatthe errors are independent. Given the status of the queries the goal is to findthe maximum likelihood order. In other words, the goal is find a permutation$\sigma$ that minimizes the number of pairs $\sigmai > \sigmaj$ where$q\sigmai,\sigmaj = -$. The problem so defined is the feedback arc setproblem on distributions of inputs, each of which is a tournament obtained as anoisy perturbations of a linear order. Note that when $\ga < 1-2$ and $n$ islarge, it is impossible to recover the original order $\pi$.It is known that the weighted feedback are set problem on tournaments isNP-hard in general. Here we present an algorithm of running time$n^{O\gamma^{-4}}$ and sampling complexity $O {\gamma}n \log n$ that withhigh probability solves the noisy sorting without re-sampling problem. We alsoshow that if $a {\sigma1},a {\sigma2},

.,a {\sigman}$ is an optimalsolution of the problem then it is ``close- to the original order. Moreformally, with high probability it holds that $\sum i |\sigmai - \pii| =\Thetan$ and $\max i |\sigmai - \pii| = \Theta\log n$.Our results are of interest in applications to ranking, such as ranking insports, or ranking of search items based on comparisons by experts.

Author: Mark Braverman, Elchanan Mossel


Related documents