Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Sorting and selection with imprecise comparisons
Ajtai M., Feldman V., Hassidim A., Nelson J. ACM Transactions on Algorithms12 (2):1-19,2015.Type:Article
Date Reviewed: Feb 1 2016

Sorting and selection with imprecise comparisons has long been the focus of extensive research attention among theoreticians. There have been a number of models and frameworks of imprecision considered in the literature. In this paper, the authors study the following simple model: when comparing two elements, the comparison is made correctly if the values of those elements differ by at least some constant &dgr;>0; otherwise, the outcome of the comparison is unpredictable.

The authors here present a number of interesting algorithmic results, as well as some useful lower bounds. They first present a deterministic max-finding algorithm with error 2 using 2n3/2 comparisons. Using this algorithm recursively, they present deterministic algorithms with error k that require comparisons. They further prove a lower bound of comparisons for the problem. They also present a linear-time randomized algorithm that achieves error 3 with probability at least 1 - 1/n2, establishing that randomization greatly changes the complexity of the problem.

Subsequently, the authors prove that the selection of an element of any order i can be achieved using comparisons, and sorting with error k can be done using comparisons. They also prove a lower bound of comparisons for sorting with error k. All of the algorithms have the same time order as the number of comparisons they make.

Notably, to obtain the algorithms for larger error k, the authors use several different ways to partition elements, recursively apply algorithms for smaller error, and then finally combine results. As noted by the authors, a similar approach to finding a small set of “good” elements was used by Borgstrom and Kosaraju [1] in the context of noisy binary search.

The model studied by the authors is inspired by both imprecision in human judgment of values and also by bounded but potentially adversarial errors in sporting tournaments, which make it all the more interesting and useful. In summary, the results achieved by the authors basically establish that there exist algorithms that are robust to imprecision in comparisons while using substantially fewer comparisons than the naive methods. Additionally, the deterministic algorithms presented here can be used in another interesting well-studied problem of finding a k-king in any tournament graph while minimizing the number of edges checked. Finally, the authors list a number of interesting and natural open problems.

Reviewer:  M. Sohel Rahman Review #: CR144140 (1604-0260)
1) Borgstrom, R. S.; Kosaraju, S. R. Comparison-based search in the presence of errors. In Proc. of the 25th Annual ACM Symposium on Theory of Computing (STOC). ACM, 1993, 130–136.
Bookmark and Share
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Nonnumerical Algorithms And Problems": Date
Improving the performance guarantee for approximate graph coloring
Wigderson A. Journal of the ACM 30(4): 729-735, 1983. Type: Article
Feb 1 1985
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
Demel J., Demlová M., Koubek V. Theoretical Computer Science 36(2-3): 203-216, 1985. Type: Article
Jan 1 1986
Complexity of the word problem for commutative semigroups of fixed dimension
Huynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy