<p>Recall from <a href="http://en.wikipedia.org/wiki/Monte_Carlo_algorithm" rel="nofollow">Wikipedia</a> 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. </p>

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

<p>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. </p>

<blockquote>
  <p>My question is whether there are terms defined to distinguish between these two types of algorithms?</p>
</blockquote>

<p>(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&lt;a&lt;b$, is the TSP optimal solution has value less than $a$ or more than $b$?)</p>

CC BY-SA 3.0
2011-10-08T08:27:59.750Z
The first type is a subset of anytime algorithms. http://en.wikipedia.org/wiki/Anytime_algorithm
Chao Xu
CC BY-SA 3.0
2011-10-08T09:03:50.280Z
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.
Dan
<ds.algorithms><randomized-algorithms>
Distinguishing two types of Monte-Carlo algorithms
Dan
# Distinguishing two types of Monte-Carlo algorithms

(Asked by: username_0 on 2011-10-05)

Recall from [Wikipedia](http://en.wikipedia.org/wiki/Monte_Carlo_algorithm) 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

**Tags:** ds.algorithms, randomized-algorithms
> **Comments:**
> **username_1**: The first type is a subset of anytime algorithms. http://en.wikipedia.org/wiki/Anytime_algorithm  
> **username_0**: 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.  

---

## 0 answers

