On reconstructing a hidden permutation

Show simple item record

dc.contributor.author Chierichetti, Flavio
dc.contributor.author Dasgupta, Anirban
dc.contributor.author Kumar, Ravi
dc.contributor.author Lattanzi, Silvio
dc.contributor.other Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
dc.coverage.spatial Dagstuhl, DE
dc.date.accessioned 2014-10-20T18:47:04Z
dc.date.available 2014-10-20T18:47:04Z
dc.date.issued 2014-09-04
dc.identifier.citation Chierichetti, Flavio; Dasgupta, Anirban; Kumar, Ravi and Lattanzi, Silvio, "On reconstructing a hidden permutation", in the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.604, Dagstuhl, DE, Sep. 4-6, 2014. en_US
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/1439
dc.description.abstract 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. en_US
dc.description.statementofresponsibility by Anirban Dasgupta et.al.,
dc.description.uri http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.604
dc.language.iso en_US en_US
dc.publisher DROPS en_US
dc.subject Mallows model en_US
dc.subject Rank aggregation en_US
dc.subject Reconstruction en_US
dc.title On reconstructing a hidden permutation en_US
dc.type Article en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account