Showing 2026Show all
3 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…
cs.DS2026
An Optimal Algorithm for Binary Closest String
Nick Fischer, Mursalin Habib
We revisit the Binary Closest String problem, which asks, given a set of binary strings , to compute a string minimizing the maximum Hamming distance to …