研讨会:可查询的不确定性问题的算法

活动

主讲人:

Thomas Erlebach教授
英国莱斯特大学计算机科学系

摘要:

Queryable uncertainty refers to settings where the input of a problem is initially not known precisely, but exact information about the input can be obtained at a cost using queries. A natural goal is then to minimize the number of the queries that are required until the precise information that has been obtained about the input is sufficient for solving the problem. The performance of an algorithm can be measured using competitive analysis, comparing the number of queries made by the algorithm to the minimum possible number of queries. We describe the witness set algorithm concept and how it yields query-competitive algorithms for minimum spanning tree and cheapest set problems under uncertainty. We also discuss the problem
variant where the algorithm can make a bounded number of simultaneous queries in each round and the goal is to minimize the number of rounds.