Hardness of Median and Center in the Ulam Metric

Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S · 2025

Read Hardness of Median and Center in the Ulam Metric by Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16437.txt.

Introduction

Fischer, Goldenberg, Habib, and Karthik settle how hard it is to find a consensus ranking, in a 2025 paper. Rank aggregation merges many orderings into one representative permutation, measured under the Ulam distance. Two tasks matter: the median, minimizing total distance, and the center, minimizing the worst distance.

Computing a center was known to be intractable; the authors now prove the median is NP-hard too, by a simple reduction from Max-Cut, confirming a published speculation. When the answer must be one of the input rankings, they show the naive quadratic algorithm is essentially optimal, closing an open problem. The proofs adapt fine-grained lower bound techniques to this setting.

Catalog record

CREATORNick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-16437

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hardness of Median and Center in the Ulam Metric Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S Abstract The classical rank aggregation problem seeks to combine a set X X of n n permutations into a single representative “consensus” permutation. In this paper, we investigate two fundamental rank aggregation tasks under the well-studied Ulam metric : computing a median permutation (which minimizes the sum of Ulam distances to X X ) and computing a center permutation (which minimizes the maximum Ulam distance to X X ) in two settings. Continuous Setting: In the continuous setting, the median/center is allowed to be any permutation. It is known that computing a center in the Ulam metric is NP-hard and we add to this by showing that computing a median is NP-hard as well via a simple reduction from the Max-Cut problem. While this result may not be unexpected, it had remained elusive until now and confirms a speculation by Chakraborty, Das, and Krauthgamer [SODA ’21] . Discrete Setting: In the discrete setting, the median/center must be a permutation from the input set. We fully resolve the fine-grained complexity of the discrete median and discrete center problems under the Ulam metric, proving that the naive O ~ ​ ( n 2 ​ L ) \widetilde{O}(n^{2}L) -time algorithm (where L L is the length of the permutation) is conditionally optimal. This resolves an open problem raised by Abboud, Bateni, Cohen-Addad, Karthik C. S., and Seddighin [APPROX ’23]. Our reductions are inspired by the known fine-grained lower bounds for similarity measures, but we face and overcome several new highly technical challenges. 1 Introduction Suppose that n judges each rank the performances of L competitors. Given these rankings, how can the judges agree on a single consensus ranking? This fundamental question lies at the heart of a class of tasks known as rank aggregation , which has applications across various fields, including social choice theory [ BCE+16 ] , bioinformatics [ LWX19 ] , information retrieval [ Har92 ] , machine learning [ LLQ+07 ] , and recommendation systems [ ODL+20 ] , among others. Formally, the judges’ rankings can be represented as a set of n permutations X\subseteq\mathcal{S}_{L} . Then, for an appropriate metric d(\cdot,\cdot) on the space of permutations \mathcal{S}_{L} , the two most prominent rank aggregation tasks are to compute a median permutation \pi_{M} which minimizes \sum_{\pi\in X}d(\pi_{M},\pi) [ Kem59 , You88 , YL78 , DKNS01 ] , or a center permutation \pi_{C} which minimizes \max_{\pi\in X}d(\pi_{C},\pi) [ BBGH15 , BBD09 , Pop07 ] . Among the metrics studied in this context, two stand out. The first one is the classic Kendall’s tau distance which measures the number of disagreeing pairs between two permutations, i.e., the number of pairs (i,j) for which one ranking orders i before j while the other orders j before i . Kendall’s tau distance is well-motivated as it satisfies several desirable properties beyond the scope of this paper (e.g., neutrality, consistency, and the extended Condorcet property [ Kem59 , WSCK12 ] ), and is also well-understood from a computational point-of-view [ DKNS01 , FKS03 ] . For example, it is known that computing the median or center of just four permutations is already NP-hard [ DKNS01 , BBD09 ] . Several approximation algorithms have also been proposed for this metric [ ACN08 , vZW07 ] , culminating in a PTAS [ KS07 , Pev00 ] for approximating the median under Kendall’s tau metric. The other key metric is the Ulam distance which measures the minimum number of relocation operations required to turn one permutation \pi into another permutation \pi^{\prime} – i.e., the minimum number of competitors whose ranks have to be adjusted in \pi so that it agrees with \pi^{\prime} . This metric offers a simpler and more practical alternative to Kendall’s tau metric for rank aggregation tasks [ CMS01 , CDK21 , CGJ21 , CDKS22 ] . Perhaps more importantly, the Ulam metric is intimately linked to the more general edit metric on arbitrary strings, which enjoys countless applications in computational biology [ Gus97 , Pev00 ] , specifically in the context of DNA storage systems [ GBC+13 , RMR+17 ] , and beyond [ Koh85 , MJC00 ] . Despite the significance of Ulam rank aggregation problems and the extensive research dedicated to them [ BBGH15 , CDK21 , CGJ21 , CDKS22 ] , some basic questions remain unanswered. This is the starting point of our paper. 1.1 Question 1: Polynomial-Time Algorithms for Ulam Median? The first basic question is whether polynomial-time algorithms exist for exactly computing the center and median permutations under the Ulam metric. For almost all string metrics, including the aforementioned Kendall’s tau metric but also metrics beyond permutations such as the Hamming metric [ FL97 , LLM+03 , AFG+23 ] or the edit metric [ dlHC00 , NR03 ] , median and center problems are well-known and easily-proven to be NP-hard. 1 1 1 A notable exception is the Hamming median problem that can trivially be solved in polynomial time by a coordinate-wise plurality vote. Quite surprisingly, while it is known that computing an Ulam center is NP-hard [ BBGH15 ] , the complexity of computing an Ulam median has remained an open question. This is not due to a lack of interest – despite the absence of an NP-hardness proof, Chakraborty, Das, and Krauthgamer have already initiated the study of approximation algorithms for the Ulam median problem [ CDK21 , CDK23 ] , achieving a 1.999-factor approximation in polynomial time. Our first contribution is that we finally provide this missing hardness proof: Theorem 1.1 . The median problem is NP-hard in the Ulam metric. 1.2 Question 2: Fine-Grained Complexity of Discrete Ulam Center and Median? How can we circumvent this new lower bound? There are two typical approaches. The first is to resort to approximation algorithms as was done in [ CDK21 , CDK23 ] . But there is a commonly-studied second option for aggregation and clustering type problems: to restrict the solution space to only the input set of permutations X and compute the best median or center from it. 2 2 2 Or alternatively, the best median/center among the permutations in another given set Y\subseteq\mathcal{S}_{L} ; this is typically referred to as the bichromatic discrete center/median problem, or also as center/median problem with facilities in the theory of clustering. All of our results also apply to these bichromatic variants. The best median or center from the input set X is typically referred to as the discrete median or the discrete center , respectively, of X . (In the same spirit, we will occasionally refer to the unrestricted median and center, discussed in the previous subsection, as the continuous median and continuous center , respectively.) Besides being a natural polynomial-time rank aggregation task, computing discrete medians or centers has two other motivations. First, it is easy to see that computing a discrete median/center yields a 2-approximation of the (continuous) median/center problems. In fact, a key observation in [ CDK21 ] is that a discrete median often provides a (2-\varepsilon) -approximation for the (continuous) median, particularly in practical DNA storage system instances where distances tend to be large. Second, the

Read the complete text