Logo image
Back
Efficient algorithms for the inverse sorting problem with bound constraints under the l∞-norm and the Hamming distance
Journal article   Peer reviewed

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

Tzu-Chin Lin, Chung-Chin Kuo, Yong-Hsiang Hsieh and Biing-Feng Wang
Journal of Computer and System Sciences, Vol.75(8), pp.451-464
12/2009
DOI: https://doi.org/10.1016/j.jcss.2009.04.005

Abstract

Algorithms Hamming distance Inverse optimization Isotonic regression lp-norm Lower bounds Sorting
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 (n log n)-time algorithm is presented. For the problem under the Hamming distance, we first show that it has an Ω (n log n)-time lower bound in the comparison model; and then, we present an O (n log n)-time algorithm. Both of the presented algorithms improve the previous upper bounds from O (n 2 ). © 2009 Elsevier Inc. All rights reserved.

Metrics

1 Record Views

Details

Logo image