Scholarlink

<p>Let us consider the following seemingly simple scenario: A finite set is given, which has a hidden total order of its elements. A player called the searcher can freely select any two elements and compare them. Furthermore, these comparisons have different positive costs that are known to the searcher in advance. The goal of the searcher is simply to find the minimum element at a minimum total cost. This combinatorial search game naturally appears as a subproblem in an approach to exact solutions of small instances of certain hard combinatorial optimization problems. We show in this note that a simple greedy strategy minimizes the worst-case total cost of the search. While this result as such might be quite expected, interestingly, the proof is not so obvious. We apply an exchange argument within a game-theoretic setting.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Note on Finding the Minimum With Non-Uniform Comparison Costs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月6日

查看全文
  • Peter Damaschke

摘要

Let us consider the following seemingly simple scenario: A finite set is given, which has a hidden total order of its elements. A player called the searcher can freely select any two elements and compare them. Furthermore, these comparisons have different positive costs that are known to the searcher in advance. The goal of the searcher is simply to find the minimum element at a minimum total cost. This combinatorial search game naturally appears as a subproblem in an approach to exact solutions of small instances of certain hard combinatorial optimization problems. We show in this note that a simple greedy strategy minimizes the worst-case total cost of the search. While this result as such might be quite expected, interestingly, the proof is not so obvious. We apply an exchange argument within a game-theoretic setting.