Selection with Monotone Comparison Costs
Sampath Kannan, Sanjeev Khanna · 2003
We consider the problem of selecting the rth -smallest element from a list of nelements under a model where the comparisons may have different costs depending on the elements being compared. This model was introduced by [3] and is realistic in the context of comparisons between complex objects. An important special case of this general cost model is one where the comparison costs are monotone in the sizes of the elements being compared. This monotone cost model covers most "natural" cost models that arise and the selection problem turns out to be the most challenging one among the usual problems for comparison-based algorithms. We present an O(log2 n)-competitive algorithm for selection under the monotone cost model. This is in contrast to an Ω (n)lower bound that is known for arbitrary comparison costs. We also consider selection under a special case of monotone costs—-the min model where the cost of comparing two elements is the minimum of the sizes. We give a randomized O(1)-competitive algorithm for the min model.