首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Scheduling Subset Tests: One-Time, Continuous, and How They Relate
【24h】

Scheduling Subset Tests: One-Time, Continuous, and How They Relate

机译:计划子集测试:一次性,连续以及它们之间的关系

获取原文
获取原文并翻译 | 示例

摘要

A test scheduling instance is specified by a set of elements, a set of tests, which are subsets of elements, and numeric priorities assigned to elements. The schedule is a sequence of test invocations with the goal of covering all elements. This formulation had been used to model problems in multiple application domains from network failure detection to broadcast scheduling. The modeling considered both SUM_e and MAX_e objectives, which correspond to average or worst-case cover times over elements (weighted by priority), and both one-time testing, where the goal is to detect if a fault is currently present, and continuous testing, performed in the background in order to detect presence of failures soon after they occur. Since all variants are NP hard, the focus is on approximations. We present combinatorial approximations algorithms for both SUM_e and MAX_e objectives on continuous and MAX_e on one-time schedules. The approximation ratios we obtain depend logarithmically on the number of elements and significantly improve over previous results. Moreover, our unified treatment of SUM_e and MAX_e objectives facilitates simultaneous approximation with respect to both. Since one-time and continuous testing can be viable alternatives, we study their relation, which captures the overhead of continuous testing. We establish that for both SUM_e and MAX_e objectives, the ratio of the optimal one-time to continuous cover times is O(log n), where n is the number of elements. We show that this is tight as there are instances with ratio Ω(log n). We provide evidence, however, by considering Zipf distributions, that the typical ratio is lower.
机译:测试调度实例由一组元素,一组测试(它们是元素的子集)以及分配给元素的数字优先级指定。时间表是一系列测试调用的序列,目的是覆盖所有元素。从网络故障检测到广播调度,该公式已用于对多个应用程序域中的问题进行建模。该建模考虑了SUM_e和MAX_e目标,它们对应于元素的平均或最坏情况的覆盖时间(按优先级加权),以及一次测试(目的是检测当前是否存在故障)和连续测试。 ,在后台执行,以便在故障发生后立即检测到故障的存在。由于所有变体都是NP硬的,因此重点放在近似值上。我们针对连续计划中的SUM_e和MAX_e目标以及一次性计划中的MAX_e提出了组合近似算法。我们获得的近似比率对数依赖于元素的数量,并且比以前的结果有明显改善。此外,我们对SUM_e和MAX_e物镜的统一处理有助于同时对两者进行近似。由于一次性测试和连续测试可能是可行的选择,因此我们研究它们之间的关系,这捕获了连续测试的开销。我们确定对于SUM_e和MAX_e目标,最佳一次与连续覆盖时间的比率为O(log n),其中n是元素数。我们证明这是紧密的,因为有些实例的比率为Ω(log n)。但是,通过考虑Zipf分布,我们提供了证据,典型比率较低。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号