Fast algorithms that work on some large percentage of possible inputs

Question

I've been wondering if research of these algorithms exists. An example, let's say I'm fine with $p$% of possible inputs of size $n$ to be unsorted. Is there an algorithm that would allow me to sort $n$ integers in sublinear time with a guarantee that $(100-p)$% of all possible inputs will be sorted.

Algorithms don't have to be linked the sorting, let's say it's optimization, is there an algorithm that will find the optimal tour for 1% of all TSP inputs of size $n$ really fast and what that algorithm is?

Is there a fundamental reason why these algorithms shouldn't exist or are hard to analyze?

Answer 1

Not quite what you're looking for but the concept of a randomized approximation scheme (RAS) is closely related and very widely studied. This is an algorithm for computing a (numerical) quantity $f(x)$ given an input $x$ and an error tolerance $\varepsilon$. With probability at least $\tfrac23$, the algorithm returns a value $\hat{f}$ such that $(1-\varepsilon)f(x)\leq\hat{f}\leq(1-\varepsilon)f(x)$. With probability at most $\tfrac13$, the algorithm either returns an answer outside that range or says, "Uh, I dunno." If the algorithm runs in time polynomial in $|x|$ (the length of the input) and $\varepsilon^{-1}$, it's called a fully polynomial randomized approximation scheme (FPRAS).

Only succeeding with probability at least $\tfrac23$ sounds pretty terrible – "Oh, wow, it's wrong one time out of every three!". However, it's easy to boost that to any satisfactory probability by running the algorithm repeatedly and taking the median answer (counting, "Uh, I dunno" as $\infty$). By a Chernoff bound, taking the median of $O(\log |x|)$ runs gives failure probability polynomial in $|x|^{-1}$ and taking the median of polynomially many runs gives exponentially small failure probability.

Answer 2

Algorithm with sublinear time will check less than 1% of array elements, thus more than 99% of array elements will remain unsorted, and chances that the entire array will become sorted are MUCH less than 1%.

You can apply the same analysis to other algorithms. So first you need to find tasks where checking less than 1% of data elements still may allow to get right answer in more than 1% of cases.