Efficient algorithms for the inverse sorting problem with bound constraints under the l∞-norm and the Hamming distance

摘要

In this paper, we study the inverse sorting problem with bound constraints under the l∞-norm and the Hamming distance. For the problem under the l∞-norm, an O(nlogn)-time algorithm is presented. For the problem under the Hamming distance, we first show that it has an Ω(nlogn)-time lower bound in the comparison model; and then, we present an O(nlogn)-time algorithm. Both of the presented algorithms improve the previous upper bounds from O(n2).