Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Ulam Median is NP-hard for Four Permutations
Mursalin Habib
We show that computing a median under the Ulam distance is NP-hard even when the input consists of exactly four permutations. Previously, NP-hardness was known only for an unbounde…
cs.CC2026
Ulam Rank Aggregation Is Hard to Approximate for Four Rankings
Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong +3
We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a ranking (permutation) minimizing the sum of its Ula…