论文标题
可调硬币
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 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.
