• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmic operations research >Greedy Algorithms for On-Line Set-Covering
【24h】

Greedy Algorithms for On-Line Set-Covering

机译：在线覆盖的贪婪算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study on-line models for the set-covering problem in which items from a ground set arrive one by one and with any such item c, the list of names of sets that contain it in the final instance is also presented possibly together with some information regarding the content of such sets. A decision maker has to select which set, among the sets containing c, has to be put in the solution in order to cover the item. Such decision has to be taken before a new item arrives and is irrevocable. The problem consists in minimizing the number of chosen sets. We first analyze some simple heuristics for the model in which only names of sets are provided. Then we show non-trivial matching upper and lower bounds for the competitive ratio in the model in which for any item that arrives the content of all sets containing it is also revealed.
机译：我们研究了一种集合覆盖问题的在线模型，在该模型中，来自地面集合的项目是一个接一个地到达的，并且与任何这样的项目c一起，还可能在最后一个实例中列出包含该集合的集合的名称列表有关此类集合内容的信息。决策者必须选择包含c的集合中的哪个集合，以便覆盖该项目。这样的决定必须在新物品到达之前并且不可撤消。问题在于最小化所选集合的数量。我们首先分析仅提供集合名称的模型的一些简单启发式方法。然后，我们在模型中显示竞争比的非平凡匹配上限和下限，在该模型中，对于任何到达的项目，还显示了包含它的所有集合的内容。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号