Ordering integers under different permutations

\(\)
The question of finding the largest integer contained between two given lists of integers is trivial when integer ordering is interpreted in its usual way. We propose a nontrivial variant wherein each ordering comparison is performed after integers have been mapped under some bijection, and analyze the computational complexity of our combinatorial problem under a family of bijections on \(\mathbb{Z}\) introduced in this paper. Deciding feasibility is strongly NP-hard but enumeration finds the optimum in polynomial time when the number of ordering comparisons is bounded by some input constant. Our main contribution is to give a polynomial time factor-preserving reduction to our problem from any cardinality maximizing combinatorial optimization problem whose constraints can be represented in polynomial time by linear lexicographic relations. The clique problem on graphs and maximum boolean satisfiability are two examples of such cardinality problems. Combining our reduction with hardness results for the clique problem, we obtain that the optimum of our problem is hard to approximate within factor \(\Omega(n^{1/2−\epsilon})\), for any \(\epsilon > 0\), where \(n\) is the maximum size of integers in the list input to our problem.

Article

Download

View Ordering integers under different permutations