Algorithms for Computing with Uncertainty: Theory and Experiments

我们应该收集多少信息才能做出决定？这个问题是具有可探索不确定性的计算的研究领域的基础。例如，假设我们要构建一个连接一组分支机构的网络。对于分支机构的任何两个位置A和B，我们根据它们之间的距离估算了在A和B之间建立链路的成本。在A和B之间建立联系的确切成本可以通过进一步的调查来确定，但这些调查需要时间和金钱。如果我们知道每一对位置的确切链路成本，我们就可以使用已知的最小生成树算法来确定构建网络的最便宜方式。然而，首先确定所有地点对之间建立链路的确切成本的方法效率不高：确定所有确切的链路成本将需要很长时间，而获得该信息的成本将是巨大的。因此，希望找到有效的方法来以聪明的方式选择需要确定其链路成本的位置对，同时仍然实现能够利用所获得的信息来构建廉价网络的目标。具有可探测不确定性的计算算法解决了这样的问题：它们指定了一种策略，用于选择应该确定准确信息的位置对，直到获得足够的信息来确定要建立的最佳可能网络。更广泛地说，具有可探索不确定性的计算处理的是部分输入是不确定的(仅大致知道)，但是可以使用查询操作以代价获得。以前关于具有不确定性的计算的工作集中在这样的设置上，即一个接一个地进行查询(这可能需要很长时间)，并且目标是在确保获得足够的信息以最优方式解决问题的同时进行尽可能少的查询。这留下了一个悬而未决的问题，即如果可以同时进行多个查询，那么应该如何选择查询，这在许多应用程序中都是现实的(例如，在上面的应用程序大纲中，可以并行确定在几对分支机构位置之间建立链接的确切成本)。另一个尚未充分考虑的方向是目标是优化查询成本和最终确定的解决方案成本的组合的设置。该项目旨在通过解决这些悬而未决的问题和开发在所述场景中被证明工作得很好的新算法，将具有可探测不确定性的计算研究提升到一个新的水平。在项目中开发的方法可能对任何决策场景都有用，在这些场景中，原则上可以获得关于问题输入数据的附加信息，并且可以通过成本获得这些信息。

How much information should we collect before making a decision? This question underlies the research area of computing with explorable uncertainty. For example, assume that we want to build a network connecting a set of branch offices. For any two locations A and B of branch offices, we have an estimate of the cost for building a link between A and B based on the distance between them. The exact cost of building a link between A and B can be determined by further investigations, but these investigations take time and cost money. If we knew the exact link cost for every pair of locations, we could determine the cheapest way of building the network using a known algorithm for the "minimum spanning tree" problem. The approach of first determining for all pairs of locations the exact cost of building a link between them is not efficient, however: It will take a long time to determine all the exact link costs, and the costs for obtaining that information will be significant. It is therefore desirable to find efficient methods for selecting in a clever way the pairs of locations for which the link costs need to be determined, while still achieving the goal of being able to build a cheap network with the information gained. Algorithms for computing with explorable uncertainty solve such problems: They specify a strategy for selecting the pairs of locations for which exact information should be determined until sufficient information has been gained to determine the best possible network to be built. More generally, computing with explorable uncertainty deals with problems where part of the input is uncertain (known only approximately) but can be obtained at a cost using a query operation.Previous work on computing with uncertainty has focused on the setting where queries are made one by one sequentially (which may take a long time) and where the goal is to make as few queries as possible while ensuring that sufficient information is obtained to solve the problem optimally. This leaves open the question of how the queries should be selected if a number of queries can be made at the same time in parallel, which is realistic in many applications (for example, in the application outlines above, the exact costs of building links between several pairs of branch office locations could be determined in parallel). Another direction that has not yet been sufficiently considered is the setting where the goal is to optimize a combination of the query cost and the cost of the solution determine in the end. The project aims to take research in computing with explorable uncertainty to the next level by addressing these open questions and developing new algorithms that work provably well in the described scenarios. Methods developed in the project can potentially be useful to any decision-making scenarios where additional information about the input data of a problem is available in principle and can be obtained at a cost.