2026-07-22T11:37:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4725 2024-03-06T10:35:19Z ddc:004 open_access

On Reconstructing a Hidden Permutation Chierichetti, Flavio Dasgupta, Anirban Kumar, Ravi Lattanzi, Silvio Mallows model; Rank aggregation; Reconstruction The Mallows model is a classical model for generating noisy perturbations of a hidden permutation, where the magnitude of the perturbations is determined by a single parameter. In this work we consider the following reconstruction problem: given several perturbations of a hidden permutation that are generated according to the Mallows model, each with its own parameter, how to recover the hidden permutation? When the parameters are approximately known and satisfy certain conditions, we obtain a simple algorithm for reconstructing the hidden permutation; we also show that these conditions are nearly inevitable for reconstruction. We then provide an algorithm to estimate the parameters themselves. En route we obtain a precise characterization of the swapping probability in the Mallows model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Flavio Chierichetti and Anirban Dasgupta and Ravi Kumar and Silvio Lattanzi 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.604 urn:nbn:de:0030-drops-47251 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.604 eng https://creativecommons.org/licenses/by/3.0/legalcode