On sorting in the presence of erroneous information (Q1199884): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(92)90203-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2000072121 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Searching with a forbidden lie pattern in responses / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3783955 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Searching with known error probability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3773361 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coping with errors in binary search procedures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4121861 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Fault-Tolerant Networks for Sorting / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:09, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On sorting in the presence of erroneous information |
scientific article |
Statements
On sorting in the presence of erroneous information (English)
0 references
17 January 1993
0 references
\textit{K. B. Lakshmanan}, \textit{B. Ravikumar} and \textit{K. Ganesan} [(*) Coping with erroneous information while sorting, IEEE Trans. Comput. 40(9), 1081-1084 (1991)] studied the following problem of sorting a given set \(X=\{x_ 1,x_ 2,\dots,x_ n\}\) of \(n\) distinct elements using binary comparisons of the form ``Is \(x_ i<x_ j\)?'', with two possible outcomes, ``yes'' and ``no'' for each comparison. However, some of the responses received for the comparisons could be erroneous. It is assumed that the number of errors can be at most \(e\), and \(e\) is known ahead of time. The authors established that if there are at most \(e\) erroneous responses, then the worst-case complexity of the sorting problem is \(\Omega(n\log n+en)\). They also presented an algorithm for the problem which requires at most \(O(n\log n+en+e^ 2)\) comparison queries. Clearly the algorithm is not optimal if \(e\) is large. We present an algorithm that uses at most \(O(n\log n+en)\) comparison queries, i.e. it matches the lower bound established in (*) for all values of \(e\).
0 references
adversary strategy
0 references
binary insertion sort
0 references
errors
0 references
lies
0 references
two-person game
0 references