1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yeah, definitely similar and has occurred to me but discovering the optimal tour for TSP with RAS should be hard so I've settled for a percentage of all possible inputs because it's less intuitive, at least to me, of how hard that is to accomplish. The wiki you linked is, on the other hand a different thing, approximating the wellness of result. $\endgroup$ – Looft Aug 20 '18 at 17:52
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.