1. bookVolume 8 (2021): Issue 15 (November 2021)
Journal Details
License
Format
Journal
eISSN
2182-1976
First Published
16 Apr 2016
Publication timeframe
2 times per year
Languages
English
access type Open Access

Adjustable Coins

Published Online: 07 Dec 2021
Volume & Issue: Volume 8 (2021) - Issue 15 (November 2021)
Page range: 27 - 39
Journal Details
License
Format
Journal
eISSN
2182-1976
First Published
16 Apr 2016
Publication timeframe
2 times per year
Languages
English
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.

[1] D. Berend et al. “Optimal ordering of independent tests with precedence constraints”. In: Discrete Applied Mathematics 162 (2014), pp. 115–127.10.1016/j.dam.2013.07.014 Search in Google Scholar

[2] S. Moran. “General approximation algorithms for some arithmetical combinatorial problems”. In: Theoretical Computer Science 14.3 (1981), pp. 289–303.10.1016/0304-3975(81)90047-5 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo