Pith. Sign in

REVIEW

Hardness of Approximation of Rank Aggregation on Ulam Metric

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Tien Long Nguyen

Computational Complexity · Submitted 29 Aug 2026 · 28 references

Pith's verdict: A sound, genuinely new reduction: explicit 51/50 inapproximability and additive-scheme impossibility for four-input Ulam median and center, needing only notational cleanup and a more readable Lemma 3.5.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 9, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 4 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2608.29180 (version 1)
Pith IDKZIOVPHG, Pith's permanent record of this paper and its review
CitationDebarati Das, Diptarka Chakraborty, Le Van Cuong, Sk Ruhul Azgor, Tien Long Nguyen. "Hardness of Approximation of Rank Aggregation on Ulam Metric." arXiv:2608.29180 (2026). https://pith.science/paper/KZIOVPHG
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Rank aggregation under the Ulam metric is hard to approximate within any constant factor better than 51/50, even for four input permutations.

The reading

This paper proves that, unless P=NP, the Ulam median and Ulam center problems cannot be approximated in polynomial time within a factor of 51/50 − ε for any ε > 0, even when the instance consists of only four permutations. It further rules out polynomial-time additive approximation schemes for both problems. These are the first explicit constant-factor inapproximability results for rank aggregation under the Ulam metric, showing that the previously known 2-approximation algorithms are essentially optimal and that no PTAS exists.

What carries the argument

The parity-sensitive gadget: two local permutations P1 = abc and P2 = bca over three symbols, whose total LCS contribution to any candidate sum over the four subsets of a given parity class equals 11 for odd parity and 10 for even parity. This gadget is embedded in an equation block for each MAX-E3-LIN-2 equation, and a large anchor block (size 2N+1) separates the equation gadget from the variable-consistency gadget, forcing any near-optimal median to correspond to a partition of the non-anchor symbols. The anchor block and stable-reordering argument allow the proof to decompose the candidate's total LCS score into independent contributions from the two gadgets, leading to an exact affine relation between median cost and optimal MAX-E3-LIN-2 value.

Extended reading notes

Core claim

For every ε > 0, it is NP-hard to approximate either Ulam median or Ulam center within a factor of 51/50 − ε, even when the input consists of four permutations. Additionally, unless P=NP, neither problem admits a polynomial-time additive approximation scheme: for median no εmn-additive approximation (with m=4) and for center no εn-additive approximation, for ε ≤ 1/300. The hardness for median is obtained via a gap-preserving reduction from MAX-E3-LIN-2; the hardness for center is then derived through a cyclic-block reduction from Ulam median that preserves the optimum value exactly.

Load-bearing premise

The proof of the affine relation between median cost and MAX-E3-LIN-2 optimum (Lemma 3.8) relies on Lemma 3.5, which assumes that any candidate permutation can be stably reordered by block and its anchor symbols replaced by the canonical order Z without decreasing any LCS score, and that every optimizing cut can be charged to a partition (S_L, S_R) separated by the central anchor z_{N+1}. If the stable-reordering or cut-decomposition claim fails for some interleaving, the 51/50 gap may not follow.

Editorial extensions

If this is right

  • No polynomial-time approximation scheme (PTAS) exists for Ulam median or Ulam center, even for four input permutations.
  • The known 2-approximation for Ulam median and Ulam center is essentially the best possible up to a factor of 51/50, closing the previous gap between algorithms and lower bounds.
  • The additive inapproximability (εmn for median, εn for center) means that even a small constant additive error cannot be achieved efficiently unless P=NP.
  • The result for four inputs is tight: Ulam median is exactly solvable in polynomial time for three inputs, marking a sharp complexity transition.
  • The cyclic-block reduction from median to center shows that the center problem inherits the same approximation hardness as the median problem, unlike other metric settings where center may be easier.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exact ratio 51/50 = 1.02 arises from the combination of the 2-gap of MAX-E3-LIN-2 (satisfiable fraction 1 vs 1/2) and the linear relation OPT_med = 26q − OPT_LIN. If a stronger inapproximability for MAX-E3-LIN-2 (e.g., 2-ε for arbitrarily small ε) had been used, the ratio would approach 1, suggesting that the factor 51/50 is not a fundamental barrier but an artifact of the specific gadget gap.
  • The parity-sensitive gadget relies on the fact that h(T) depends only on the parity class when averaged over the four offset copies. This symmetrization technique may be applicable to other aggregation problems where local scores depend on more than parity but average out over a full affine shift.
  • The stable-reordering argument in Lemma 3.5, which forces anchor symbols into the canonical order Z without decreasing LCS, is the most fragile step. Proving or disproving it for different interleavings could either strengthen the hardness or reveal a hidden algorithmic opening.
Original abstract

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a permutation minimizing the sum of its Ulam distances to the input permutations, while in the \emph{Ulam center} problem the objective is to minimize the maximum such distance. Both problems are known to be NP-hard, but no explicit approximation hardness was previously known. We prove that, for every $\varepsilon>0$, it is NP-hard to approximate either Ulam median or Ulam center within a factor of $51/50-\varepsilon$, even when the input consists of only four permutations. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. The hardness result for Ulam median is established via a reduction from MAX-E3-LIN-2. The corresponding hardness for Ulam center is then obtained through a reduction from Ulam median.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,548 input tokens.

What the abstract itself states, as probabilities: claims first 0.51 · states limitation 0.24 · human participants 0.02 · controlled comparison 0.01 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.69 · mentions code or data availability 0.01.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a permutation minimizing the sum of its Ulam distances to the input permutations, while in the \emph{Ulam center} problem the objective is to minimize the maximum such distance. Both problems are known to be NP-hard, but no explicit approximation hardness was previously known. We prove that, for every $\varepsilon>0$, it is NP-hard to approximate either Ulam median or Ulam center within a factor of $51/50-\varepsilon$, even when the input consists of only four permutations. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. The hardness result for Ulam median is established via a reduction from MAX-E3-LIN-2. The corresponding hardness for Ulam center is then obtained through a reduction from Ulam median.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 We study the approximability of rank aggregation under the Ulam metric. contribution 0.66 0.64 0.04 asserted 0.54
s1 In the \emph{Ulam median} problem, the goal is to find a permutation minimizing the sum of its Ulam distances to the input permutations, while in the \emph{Ulam center} problem the objective is to minimize the maximum such distance. background 1.00 0.07 0.03 asserted 0.98
s2 Both problems are known to be NP-hard, but no explicit approximation hardness was previously known. gap 0.97 0.05 0.03 asserted 1.00
s3 We prove that, for every $\varepsilon>0$, it is NP-hard to approximate either Ulam median or Ulam center within a factor of $51/50-\varepsilon$, even when the input consists of only four permutations. result 0.96 0.97 0.91 asserted 1.00
s4 We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. result 0.96 0.93 0.16 asserted 0.99
s5 The hardness result for Ulam median is established via a reduction from MAX-E3-LIN-2. method 0.99 0.91 0.04 asserted 1.00
s6 The corresponding hardness for Ulam center is then obtained through a reduction from Ulam median. method 0.98 0.93 0.04 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. The two-level decomposition used in Lemma
Figure 2. The median-to-center reduction for m = 4. Cyclic shifts place every original input once in every row and column, preserving the optimum. Lemma 4.1 (Median-to-center reduction). There is a polynomial-time algorithm that, given an instance Π = {πj} m−1 j=0 of Ulam median over an alphabet Σ of size n, constructs an instance C(Π) = {σj} m−1 j=0 of Ulam center consisting of m permutations over an alphabet Σ ′ of size mn such that OPTctr(C(Π)) = OPTmed(Π). Moreover, from any center solution for C(Π) of radius at most R, one can compute in polynomial time a permutation ρ ∈ P(Σ) with…

Figures reproduced from arXiv:2608.29180 by the authors.

References
How the literature uses it

What this paper does with the arXiv papers it cites

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

What it cites · 4 sentences without a confident label

Compares with 2 papers

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.