• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Congress on Evolutionary Computation >On asymptotic complexity of the optimum Golomb ruler problem: From established stochastic methods to self-avoiding walks
【24h】

On asymptotic complexity of the optimum Golomb ruler problem: From established stochastic methods to self-avoiding walks

机译：最佳Golomb尺子问题的渐近复杂性：从建立的随机方法到自我避免的游走

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Optimum or near-optimum solutions of the Golomb ruler (gr) problem have applications in information theory, error correction, current transformers, radio frequency selection, placement of antenna arrays in astronomy, among others. In mathematics, there is a well-defined relationship of Golomb rulers and graceful graphs. A massively parallel computing project on gr has been on-going for more than 10 years: the order-24 ruler was claimed as optimum in November 2004 (after a 4-year computational effort), followed by order-25, -26, -27 rulers in 2008, 2009, 2014. The order-28 ruler is work-in-progress. The distribution of waiting times, in years, such as {4, 4, 1, 5} may be impossible to predict under a variable number of processors running simultaneously. This paper proposes a model to experimentally predict the asymptotic runtime complexity of any gr solver that returns the best-known-value (BKV) Golomb ruler defined by the paired list (L = length, M = order). A subset of this list includes {(6,4), (11,5), (17,6), (25,7), (34,8), (44,9),..., (680,30)}. Given the number of processors N and the runtime limit t, we observe at least N ≥ 100 processors reaching the target BKV with the first-passage-time <; t and say that each such observation is uncensored. In other words, the mean runtime value we measure is based strictly on at least 100 uncensored observations from the experiment. Experiments in this paper focus on a stochastic gr-solver that implements a variation of a self-avoiding walk. In the total number of steps, the solver asymptotic walkLength complexity is 409.2 × 1.0762. When measuring the number of CPU seconds on a loaded grid of 100 processors, the solver asymptotic runtime complexity is 0.000206 × 1.08711. This solver significantly outperforms the alternative stochastic gr-solvers reported to date.
机译：哥伦布尺子（gr）问题的最佳或接近最佳解决方案在信息论，纠错，电流互感器，射频选择，天文学中天线阵列的放置等方面都有应用。在数学中，哥伦布尺和优美图之间有明确定义的关系。关于gr的大规模并行计算项目已经进行了10多年：在经过4年的计算工作之后，第24阶标尺在2004年11月被认为是最优的，其后是第25阶，-26，- 2008年，2009年和2014年有27个标尺。28号标尺在进行中。在可变数量的同时运行的处理器下，可能无法预测等待时间的分布（例如{4，4，1，5}），以年为单位。本文提出了一个模型，通过实验预测任何gr求解器的渐近运行时复杂度，这些求解器将返回由配对列表定义的最佳已知值（BKV）Golomb标尺（L =长度，M =顺序）。此列表的子集包括{（6,4），（11,5），（17,6），（25,7），（34,8），（44,9），...，（680， 30）}。给定处理器数量N和运行时间限制t，我们观察到至少N≥100个处理器以第一次通过时间<;达到了目标BKV。并说每个这样的观察都是未经审查的。换句话说，我们测量的平均运行时间值严格基于实验中至少100个未经审查的观察值。本文中的实验着重于一种随机的gr-solver，它实现了一种自动回避行走的变体。在总步数中，求解器的渐近walkLength复杂度为409.2×1.0762。在100个处理器的已加载网格上测量CPU秒数时，求解器的渐近运行时复杂度为0.000206×1.08711。该求解器明显优于迄今报道的其他随机gr-solver。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号