Source-linked AI summary
Hardness of Approximation of Rank Aggregation on Ulam Metric
Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Tien Long Nguyen
TL;DR
The paper asks how well Ulam median and Ulam center can be approximated, given that explicit approximation hardness was previously unknown. It uses a MAX-E3-LIN-2 reduction for median and a reduction from median to center, proving strong hardness even with four permutations and ruling out additive approximation schemes.
Problem
Explicit approximation hardness was previously unknown for Ulam median and Ulam center, despite both problems being NP-hard.
Method
The paper reduces MAX-E3-LIN-2 to Ulam median using a parity-sensitive gadget, then reduces Ulam median to Ulam center.
Results
51/50 −ε inapproximability holds for both Ulam median and Ulam center with four input permutations, and neither admits a polynomial-time additive approximation scheme unless P = NP.
Takeaways & Limitations
Four-permutation Ulam aggregation is already hard to approximate, and the same reductions exclude PTAS-style and additive approximation schemes.
Takeaways & Limitations
The paper leaves open stronger hardness for an arbitrary number of inputs and whether Ulam center can beat factor 2 when the input count is variable.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper establishes explicit approximation hardness for Ulam median and center, even with four input permutations, and rules out polynomial-time approximation schemes and additive approximation schemes unless P = NP.
- Approximation hardness: 51/50 −ε hardness holds for Ulam median with four input permutations.This is stated for every ε > 0 unless P = NP.
- 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.
- 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.
- 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.
- 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.
- 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.
2 Preliminaries
The preliminaries define permutations, Ulam distance, the median and center objectives, approximation schemes, and the MAX-E3-LIN-2 source problem used in the hardness reduction.
- 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.
- 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(Π).
- Aggregation objectives: Ulam center minimizes the maximum distance from a consensus permutation to any input permutation.Its objective is the radius radΠ(σ), with optimum OPTctr(Π).
- 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.
- 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).
3 Hardness of Approximation for Ulam Median
The Ulam median is shown to resist approximation within 51/50 − ε, even with four input permutations, via a gap-preserving reduction from MAX-E3-LIN-2. The construction converts equation satisfaction into median-score gaps using parity and variable-consistency gadgets, then rules out polynomial-time additive approximation schemes.
- Unless P=NP, no polynomial-time algorithm approximates Ulam median within 51/50 − ε for any ε > 0, even with four input permutations.
- 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.
- 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.
- Equation gadget: 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.
- 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.
4 Hardness of Approximation for Ulam Center
The paper reduces Ulam median to Ulam center using a cyclic block construction that preserves the optimum and enables lossless solution extraction. This transfers a 51/50−ε inapproximability bound and rules out εn-additive approximation for four-input Ulam center.
- 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.
- 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.
- Median-to-center reduction: 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.
- 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.
- 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.
- 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.
5 Conclusion
The paper establishes explicit constant-factor inapproximability for Ulam median and center, even with four inputs, and also rules out polynomial-time additive approximation schemes. Its results leave a substantial gap to existing approximation algorithms and identify stronger hardness for unrestricted input counts as an open direction.
- 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.
- Main conclusions: The same linear gap rules out polynomial-time additive approximation schemes for these problems.This extends the multiplicative hardness conclusion to additive guarantees.
- 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.