Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Chierichetti, Flavio; Dasgupta, Anirban; Kumar, Ravi; Lattanzi, Silvio License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-47251

; ; ;

On Reconstructing a Hidden Permutation



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.

BibTeX - Entry

  author =	{Flavio Chierichetti and Anirban Dasgupta and Ravi Kumar and Silvio Lattanzi},
  title =	{{On Reconstructing a Hidden Permutation}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{604--617},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-47251},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.604},
  annote =	{Keywords: Mallows model; Rank aggregation; Reconstruction}

Keywords: Mallows model; Rank aggregation; Reconstruction
Seminar: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI