Selection with monotone comparison costs

ABSTRACT

We consider the problem of selecting the r^th-smallest element from a list of n elements 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(log² 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.

REFERENCES

• 1: Noga Alon , Manuel Blum , Amos Fiat , Sampath Kannan , Moni Naor , Rafail Ostrovsky, Matching nuts and bolts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.690-696, January 23-25, 1994, Arlington, Virginia, United States
• 2: Noga Alon , Phillip G. Bradford , Rudolf Fleischer, Matching nuts and bolts faster, Information Processing Letters, v.59 n.3, p.123-127, Aug. 12, 1996 [doi>10.1016/0020-0190(96)00104-4]
• 3: Moses Charikar , Ronald Fagin , Venkatesan Guruswami , Jon Kleinberg , Prabhakar Raghavan , Amit Sahai, Query strategies for priced information (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.582-591, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335382]
• 4: A. Gupta , A. Kumar, Sorting and Selection with Structured Costs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.416, October 14-17, 2001
• 5: J. HARTLINE, E. HONG, A. MOHR, E. ROCKE, AND K. YASUHARA. As reported in {3}. Nov. 2000.
• 6: János Komlós , Yuan Ma , Endre Szemerédi, Matching nuts and bolts in O(n log n) time, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.232-241, January 28-30, 1996, Atlanta, Georgia, United States
• 7: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Theory