Optimal dislocation with persistent errors in subquadratic time

DOI10.1007/s00224-019-09957-5zbMath1433.68111OpenAlexW2993963457WikidataQ126667258 ScholiaQ126667258MaRDI QIDQ1987515

Stefano Leucci, Barbara Geissmann, Chih-Hung Liu, Paolo Penna

Publication date: 15 April 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8526/

zbMATH Keywords

sortingmaximum dislocationrecurrent comparison errors

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Related Items (3)

External-memory sorting with comparison errors ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Approximate minimum selection with unreliable comparisons

Cites Work

• Unnamed Item
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Recursive merge sort with erroneous comparisons
• The tail of the hypergeometric distribution
• Sorting by swaps with noisy comparisons
• The Solution Space of Sorting with Recurring Comparison Faults
• Tolerant Algorithms
• Sorting and Selection with Imprecise Comparisons
• Computing with Noisy Information
• Sorting from Noisier Samples
• Quicksort with Unreliable Comparisons: A Probabilistic Analysis
• Sorting with Recurrent Comparison Errors
• Ordering by weighted number of wins gives a good ranking for weighted tournaments
• Searching games with errors -- fifty years of coping with liars

This page was built for publication: Optimal dislocation with persistent errors in subquadratic time