<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>In this paper we consider a scenario where there are several algorithms for solving a given problem. Each algorithm is associated with a probability of success and a cost, and there is also a penalty for failing to solve the problem. The user may run one algorithm at a time for the specified cost, or give up and pay the penalty. The probability of success may be implied by randomization in the algorithm, or by assuming a probability distribution on the input space, which lead to different variants of the problem. The goal is to minimize the expected cost of the process under the assumption that the algorithms are independent. We study several variants of this problem, and present possible solution strategies and a hardness result.</p>
</abstract>

In this paper we consider a scenario where there are several algorithms for solving a given problem. Each algorithm is associated with a probability of success and a cost, and there is also a penalty for failing to solve the problem. The user may run one algorithm at a time for the specified cost, or give up and pay the penalty. The probability of success may be implied by randomization in the algorithm, or by assuming a probability distribution on the input space, which lead to different variants of the problem. The goal is to minimize the expected cost of the process under the assumption that the algorithms are independent. We study several variants of this problem, and present possible solution strategies and a hardness result.

Adjustable Coins

Recreational Mathematics Magazine

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"Adjustable Coins"}

In this paper we consider a scenario where there are several algorithms for solving a given problem. Each algorithm is associated with a probability of success...

Adjustable Coins

Publié en ligne: 07 déc. 2021

Pages: 27 - 39

DOI: https://doi.org/10.2478/rmm-2021-0009

© 2021 Shlomo Moran et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.