6 citations · 6 across the 3 of their papers we have counts for
5 papers · 1 filter
An Optimal Sorting Algorithm for Persistent Random Comparison Faults
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We consider the problem of sorting elements subject to persistent random comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (…
Longest Increasing Subsequence under Persistent Comparison Errors
Barbara Geissmann
We study the problem of computing a longest increasing subsequence in a sequence of distinct elements in the presence of persistent comparison errors. In this model, every…
Optimal Sorting with Persistent Comparison Errors
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We consider the problem of sorting elements in the case of \emph{persistent} comparison errors. In this model (Braverman and Mossel, SODA'08), each comparison between two eleme…
Sorting with Recurrent Comparison Errors
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sort…
Counting small cuts in a graph
Barbara Geissmann, Rastislav Šrámek
We study the minimum cut problem in the presence of uncertainty and show how to apply a novel robust optimization approach, which aims to exploit the similarity in subsequent graph…