Back to Search Start Over

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

Authors :
Yong-Hsiang Hsieh
Biing-Feng Wang
Chung-Chin Kuo
Tzu-Chin Lin
Source :
Journal of Computer and System Sciences. 75:451-464
Publication Year :
2009
Publisher :
Elsevier BV, 2009.

Abstract

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 @W(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(n^2).

Details

ISSN :
00220000
Volume :
75
Database :
OpenAIRE
Journal :
Journal of Computer and System Sciences
Accession number :
edsair.doi...........d142d36d53836217cde1e99ae90290b9