Longest increasing subsequence under persistent comparison errors

DOI10.1007/978-3-030-04693-4_16zbMath1444.68306arXiv1808.03307OpenAlexW3177225655MaRDI QIDQ5916089

Barbara Geissmann

Publication date: 15 January 2019

Published in: Theory of Computing Systems, Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.03307

zbMATH Keywords

approximation algorithmlower boundslongest increasing subsequenceprobabilistic persistent comparison errors

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Uses Software

• MUMMER

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating longest increasing subsequences and patience sorting
• Recursive merge sort with erroneous comparisons
• A fast algorithm for computing a longest common increasing subsequence
• A faster algorithm computing string edit distances
• On computing the length of longest increasing subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• Fast computation of a longest increasing subsequence and application
• Optimal dislocation with persistent errors in subquadratic time
• Structural filtering: a paradigm for efficient and exact geometric programs
• Finding longest increasing and common subsequences in streaming data
• The Solution Space of Sorting with Recurring Comparison Faults
• Tolerant Algorithms
• Data Streams: Algorithms and Applications
• Sorting and Selection with Imprecise Comparisons
• Design and implementation of an efficient priority queue
• On the distribution of the length of the longest increasing subsequence of random permutations
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Computing with Noisy Information
• Quicksort with Unreliable Comparisons: A Probabilistic Analysis
• Inversions from Sorting with Distance-Based Errors
• Sorting with Recurrent Comparison Errors

This page was built for publication: Longest increasing subsequence under persistent comparison errors