TY - GEN

T1 - Noisy sorting without resampling

AU - Braverman, Mark

AU - Mossel, Elchanan

PY - 2008

Y1 - 2008

N2 - In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order aπ(1) < ... < aπ(n) where π is a permutation on n elements. The input is the status of (n/2) queries of the form q(ai,aj), for i < j, where q(ai, a j) = +(-) with probability 1/2 + γ if π(i) > π(j)(π(i) < π(j)) for all pairs i ≠ where γ > 0 is a constant. It is assumed that the errors are independent. Given the status of the queries the goal is to find the maximum likelihood order. In other words, the goal is find a permutation σ that minimizes the number of pairs σ(i) > σ(j) where q(σ(i), σ(j)) = -. The problem so defined is the feedback arc set problem on distributions of inputs, each of which is a tournament obtained as a noisy perturbation of a linear order. Note that when γ >1/2 and n is large, it is impossible to recover the original order π. It is known that the weighted feedback arc set problem on tournaments is NP-hard in general. Here we present an algorithm of running time n O(γ-4) and sampling complexity Oγ (n log n) that with high probability solves the noisy sorting without re-sampling problem. We also show that if aσ(i), aσ(2),..., aσ(n) is an optimal solution of the problem then it is "close" to the original order. More formally, with high probability it holds that Σ|σ(i) -π(i)| = Θ(n), max|σ(i) - π(i)| = Θ(log n).

AB - In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order aπ(1) < ... < aπ(n) where π is a permutation on n elements. The input is the status of (n/2) queries of the form q(ai,aj), for i < j, where q(ai, a j) = +(-) with probability 1/2 + γ if π(i) > π(j)(π(i) < π(j)) for all pairs i ≠ where γ > 0 is a constant. It is assumed that the errors are independent. Given the status of the queries the goal is to find the maximum likelihood order. In other words, the goal is find a permutation σ that minimizes the number of pairs σ(i) > σ(j) where q(σ(i), σ(j)) = -. The problem so defined is the feedback arc set problem on distributions of inputs, each of which is a tournament obtained as a noisy perturbation of a linear order. Note that when γ >1/2 and n is large, it is impossible to recover the original order π. It is known that the weighted feedback arc set problem on tournaments is NP-hard in general. Here we present an algorithm of running time n O(γ-4) and sampling complexity Oγ (n log n) that with high probability solves the noisy sorting without re-sampling problem. We also show that if aσ(i), aσ(2),..., aσ(n) is an optimal solution of the problem then it is "close" to the original order. More formally, with high probability it holds that Σ|σ(i) -π(i)| = Θ(n), max|σ(i) - π(i)| = Θ(log n).

UR - http://www.scopus.com/inward/record.url?scp=58449083612&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449083612&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449083612

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 268

EP - 276

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -