Hardness of Approximation of Rank Aggregation on Ulam Metric

Approximation hardness

• 51/50 −ε hardness holds for Ulam median with four input permutations.This is stated for every ε > 0 unless P = NP.Source: §1.1 · p. 2

Additive approximation

• εmn-additive approximation is ruled out for Ulam median with four inputs for any 0 < ε ≤1/300.The reduction produces a gap linear in the total input length mn.Source: §1.1 · p. 2

Input-size boundary

• The four-input threshold is sharp: Ulam median is polynomial-time solvable exactly for three inputs but becomes constant-factor inapproximable with four.The comparison highlights the computational significance of requiring the median itself to be a permutation.Source: §1.1 · pp. 2–3

Approximation hardness

• 51/50 −ε hardness also holds for Ulam center with four input permutations.The center result is obtained through a reduction from Ulam median.Source: §1.1 · p. 3

Additive approximation

• εn-additive approximation is ruled out for Ulam center with four inputs for any 0 < ε ≤1/300.This matches the same four-input restriction as the multiplicative hardness result.Source: §1.1 · p. 3

Technical approach

• The median reduction uses a parity-sensitive gadget and yields an exact affine relation to MAX-E3-LIN-2.The construction handles arbitrary symbol partitions by decoding a majority assignment and comparing its LCS score with the induced assignment.Source: §1.2 · pp. 3–4

Permutations and Ulam distance

• Ulam distance between permutations is defined through longest common subsequences and the associated permutation transformations.For permutations over an alphabet, it is based on n minus the LCS length.Source: §2 · pp. 4–5

Aggregation objectives

• Ulam median minimizes the sum of distances from a consensus permutation to the input permutations.Its objective is denoted costΠ(σ), with optimum OPTmed(Π).Source: §2 · p. 5
• Ulam center minimizes the maximum distance from a consensus permutation to any input permutation.Its objective is the radius radΠ(σ), with optimum OPTctr(Π).Source: §2 · p. 5

Approximation schemes

• A PTAS achieves a multiplicative (1 + ε) guarantee in polynomial time for every constant ε > 0.The additive schemes instead permit εmn error for median or εn error for center.Source: §2 · p. 5

Hardness source

• MAX-E3-LIN-2 maximizes the number of satisfied three-variable parity equations over Boolean assignments.Each equation has the form xj,1 ⊕xj,2 ⊕xj,3 = λj, and the optimum is OPTLIN(E).Source: §2 · p. 5

• Unless P=NP, no polynomial-time algorithm approximates Ulam median within 51/50 − ε for any ε > 0, even with four input permutations.Source: §3 · p. 6
• The reduction from MAX-E3-LIN-2 combines equation gadgets, variable-consistency gadgets, and a long common anchor block.The equation gadget rewards satisfying assignments, consistency gadgets enforce equal truth values across occurrences, and the anchor separates the two components in an optimal median.Source: §3 · p. 6, §3.2 · p. 8

Equation gadget

• The four odd-cardinality subsets of three symbols have total score 11, while the four even-cardinality subsets have total score 10.This one-unit parity gap is the local mechanism used to encode whether an equation is satisfied.Source: §3.1 · p. 6
• For an assignment F, the constructed score satisfies u(S_F) = 10q + valLIN(E, F), so each satisfied equation contributes one additional unit.Translation by the assignment parity maps the four gadget copies to the odd or even parity class, yielding scores 11 or 10 respectively.Source: §3.3 · pp. 10, 12

Additive hardness

• The reduction creates a linear-in-mn gap, ruling out polynomial-time εmn-additive approximation for Ulam median when m = 4 and 0 < ε ≤ 1/300.Such an additive algorithm would distinguish MAX-E3-LIN-2 instances with nearly all equations satisfiable from those with at most a 1/2 + δ fraction satisfiable.Source: §3.6 · p. 17

Multiplicative hardness

• Unless P = NP, Ulam center cannot be approximated within 51/50−ε for any ε > 0, even with four input permutations.An approximation for center would contradict the corresponding hardness theorem for four-input Ulam median.Source: §4 · pp. 17, 19

Median-to-center reduction

• The median-to-center reduction maps m median inputs to m center permutations over m disjoint alphabet copies while preserving the optimum value exactly.Each center permutation contains one copy of every original input, cyclically shifted across blocks.Source: §4 · p. 18
• Stable sorting any center candidate into the common block order does not increase its distance to any center input.The common block order lets longest common subsequences decompose across blocks.Source: §4 · pp. 18–19

Optimality preservation

• Every center candidate has radius at least OPTmed(Π), while an optimal median replicated across blocks has radius OPTmed(Π), proving OPTctr(C(Π)) = OPTmed(Π).The reverse inequality follows by placing the optimal median in every alphabet copy.Source: §4 · p. 19

Solution extraction

• A center solution of radius at most R yields, in polynomial time, a median solution of cost at most R by examining the blockwise restrictions.At least one extracted block candidate has median cost no larger than the center radius.Source: §4 · pp. 18–19

Additive hardness

• Unless P = NP, no polynomial-time εn-additive approximation exists for Ulam center when m = 4 and 0 < ε ≤ 1/300.The reduction uses four center permutations of length n = 4ℓ and transfers the additive guarantee back to median.Source: §4 · p. 19

Main conclusions

• Unless P = NP, neither Ulam median nor Ulam center admits a PTAS, even with only four input permutations.The median proof uses an affine parity gadget, reversed polarity blocks, and a long anchor; the center reduction preserves the optimum and permits lossless extraction.Source: §5 · p. 20
• The same linear gap rules out polynomial-time additive approximation schemes for these problems.This extends the multiplicative hardness conclusion to additive guarantees.Source: §5 · p. 20

Open directions

• The paper identifies narrowing the gap to the best known approximation algorithms and proving stronger hardness for arbitrary input counts as important next steps.For Ulam center, whether factor 2 can be beaten when the number of inputs is part of the input remains open.Source: §5 · p. 20