The Update Complexity of Selection and Related Problems
The Update Complexity of Selection and Related Problems
复制标题
选择的更新复杂度及相关问题
DOI：
10.1007/s00224-015-9664-y
复制
发表时间：
2011
影响因子：
0.5
通讯作者：
Sandeep Sen
中科院分区：
文献类型：
--
作者：
Manoj Gupta;Yogish Sabharwal;Sandeep Sen
我们提出了一个框架，用于计算与输入数据指定的区间，表示输入参数的值的不确定性。为了计算解，该算法可以查询以子区间的形式产生更精细估计的输入参数，目标是最小化查询的数量。前面的方法解决了每个查询都返回精确值的情况。我们的框架是更一般的，因为它可以处理更广泛的各种输入和查询响应，我们建立有趣的关系，他们之间还没有被调查过。虽然以前的限制模型的一些方法可以适应更一般的模型，我们需要更复杂的技术进行分析，我们也得到了改进的算法，以前的模型。我们解决选择问题的广义模型，并表明存在2更新的竞争算法，不依赖于子区间的长度或分布，并保持对最坏情况下的对手。我们也得到了类似的界限上的竞争比图中的MST问题。
We present a framework for computing with input data specified by intervals, representing uncertainty in the values of the input parameters. To compute a solution, the algorithm can query the input parameters that yield more refined estimates in the form of sub-intervals and the objective is to minimize the number of queries. The previous approaches address the scenario where every query returns an exact value. Our framework is more general as it can deal with a wider variety of inputs and query responses and we establish interesting relationships between them that have not been investigated previously. Although some of the approaches of the previous restricted models can be adapted to the more general model, we require more sophisticated techniques for the analysis and we also obtain improved algorithms for the previous model. We address selection problems in the generalized model and show that there exist 2-update competitive algorithms that do not depend on the lengths or distribution of the sub-intervals and hold against the worst case adversary. We also obtain similar bounds on the competitive ratio for the MST problem in graphs.