Abstract
We study the problem of approximating a center under the Ulam metric. The Ulam metric, defined over a set of permutations over [n], is the minimum number of move operations (deletion plus insertion) to transform one permutation into another. The Ulam metric is a simpler variant of the general edit distance metric. It provides a measure of dissimilarity over a set of rankings/permutations. In the center problem, given a set of permutations, we are asked to find a permutation (not necessarily from the input set) that minimizes the maximum distance to the input permutations. This problem is also referred to as maximum rank aggregation under Ulam. So far, we only know of a folklore 2approximation algorithm for this NPhard problem. Even for constantly many permutations, we do not know anything better than an exhaustive search over all n! permutations.
In this paper, we achieve a (3/2  1/(3m))approximation of the Ulam center in time n^O(m² ln m), for m input permutations over [n]. We therefore get a polynomial time bound while achieving better than a 3/2approximation for constantly many permutations. This problem is of special interest even for constantly many permutations because under certain dissimilarity measures over rankings, even for four permutations, the problem is NPhard.
In proving our result, we establish a surprising connection between the approximate Ulam center problem and the closest string with wildcards problem (the center problem over the Hamming metric, allowing wildcards). We further study the closest string with wildcards problem and show that there cannot exist any (2ε)approximation algorithm (for any ε > 0) for it unless 𝖯 = NP. This inapproximability result is in sharp contrast with the same problem without wildcards, where we know of a PTAS.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2021.12,
author = {Chakraborty, Diptarka and Gajjar, Kshitij and Jha, Agastya Vibhuti},
title = {{Approximating the Center Ranking Under Ulam}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {12:112:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772150},
ISSN = {18688969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15523},
URN = {urn:nbn:de:0030drops155230},
doi = {10.4230/LIPIcs.FSTTCS.2021.12},
annote = {Keywords: Center Problem, Ulam Metric, Edit Distance, Closest String, Approximation Algorithms}
}
Keywords: 

Center Problem, Ulam Metric, Edit Distance, Closest String, Approximation Algorithms 
Collection: 

41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) 
Issue Date: 

2021 
Date of publication: 

29.11.2021 