3
$\begingroup$

Recall from Wikipedia that Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability. Consider the following two types of Monte Carlo algorithms.

  • Type-1 algorithms: When an algorithm fails, it still outputs a feasible solution.
  • Type-2 algorithms: When an algorithm fails, it outputs any arbitrary solution which might not even be feasible.

As an example, consider algorithms for, say Travelling Salesman Problem (TSP), where it outputs some value supposed to be an optimal TSP value. Type-1 algorithms are algorithms that either output the value of the optimal solution correctly or otherwise output the value of some Hamiltonian tour. Type-2 algorithms are algorithms that either output the optimal solution correctly or otherwise output an arbitrary number.

My question is whether there are terms defined to distinguish between these two types of algorithms?

(Note: One point of asking this question is that type-1 algorithms can be used to answer the following gap question with one-sided error while type-2 algorithms cannot: For some parameters $0<a<b$, is the TSP optimal solution has value less than $a$ or more than $b$?)

$\endgroup$
  • 1
    $\begingroup$ The first type is a subset of anytime algorithms. en.wikipedia.org/wiki/Anytime_algorithm $\endgroup$ – Chao Xu Oct 8 '11 at 8:27
  • 1
    $\begingroup$ Thanks for the link. It's interesting. However, I think the first type is not really a subset of anytime algorithms since it doesn't guarantee to give a valid solution at anytime but just guarantee to give a valid (feasible) solution when it terminates. $\endgroup$ – Danu Oct 8 '11 at 9:03

Your Answer

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

Browse other questions tagged or ask your own question.