...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Optimal covering designs: complexity results and new bounds
【24h】

Optimal covering designs: complexity results and new bounds

机译：最佳覆盖设计：复杂性结果和新界限

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

摘要

In this paper we investigate the problem of computing optimal lottery schemes. From a computational complexity point of view, we prove that the variation of this problem in which the sets to be covered are specified in the input is log T -approximable (where denotes the collection of sets to be covered) and it cannot be approximated within a factor smaller than log T, unless P = Np. From a combinatorial point of view, we propose new constructions based on the combination of the partitioning technique and of known results regarding the construction of sets of coverings. By means of this combination we will be able to improve several upper bounds on the cardinality of optimal lottery schemes. (C) 2004 Elsevier B.V. All rights reserved.
机译：在本文中，我们研究了计算最佳彩票方案的问题。从计算复杂度的角度来看，我们证明了在输入中指定要覆盖的集合的问题的变体是log T -approximable（其中表示要覆盖的集合的集合），并且不能除非P = Np，否则近似值应小于log T 。从组合的角度来看，我们基于分区技术和有关覆盖集构建的已知结果的组合，提出了新的构造。通过这种组合，我们将能够改善最佳彩票方案的基数的几个上限。 （C）2004 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号