专栏首页arxiv.org翻译专栏项链的 K 中心问题(cs.DS)
原创

项链的 K 中心问题(cs.DS)

在图论中,k-中心问题的目标是找到一组 k 顶点,其中任何点与其在K-集合中距其最近的点的最大距离最小化。在本文中,我们介绍了项链集的k-中心问题,即循环移位下词的等价类。这可以被看作是完整加权图上的 k-中心问题,其中每个项链都由点表示,并且每个边都含有一个权重:由每一对项链的重叠距离决定。与图例相似的是,目标是选择 k个项链,就可以类比成将语句中任何单词与其最近的中心之间的距离降至最低。但是,当k-中心问题与语言相关时,产生图的大小可能是相对于语言描述呈指数化趋势。举个例子来说,单词 l 的长度和字母 q 的大小。我们针对项链上的 k-中心问题推导出多个近似算法,在 l 和 k 上下文中具有对数级的近似因子,并且在更局限的情况下包含于恒定因子内。

原文标题:The K-Centre Problem for Necklaces

原文:In graph theory, the objective of the k-centre problem is to find a set of k vertices for which the largest distance of any vertex to its closest vertex in the k-set is minimised. In this paper, we introduce the k-centre problem for sets of necklaces, i.e. the equivalence classes of words under the cyclic shift. This can be seen as the k-centre problem on the complete weighted graph where every necklace is represented by a vertex, and each edge has a weight given by the overlap distance between any pair of necklaces. Similar to the graph case, the goal is to choose k necklaces such that the distance from any word in the language and its nearest centre is minimised. However, in a case of k-centre problem for languages the size of associated graph maybe exponential in relation to the description of the language, i.e., the length of the words l and the size of the alphabet q. We derive several approximation algorithms for the k-centre problem on necklaces, with logarithmic approximation factor in the context of l and k, and within a constant factor for a more restricted case.

原文作者:Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

原文地址:http://arxiv.org/abs/2005.10095

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 多目标进化算法应用于提高医药数据领域学习器的性能(CS AI)

    原文标题完整翻译:多目标进化算法应用于提高在医药数据领域使用整体特征选择和离散化模型的学习器的性能

    Donuts_choco
  • 针对网上资源分配机制设计的统一方法(cs.GT)

    这篇论文是关于网上资源分配在战略制定方面的机制设计。在该设定中,一个单独的供应者通过分配有限量的资源以求资源以顺序任意的方式到达。代理者则与每一个请求息息相关。...

    Donuts_choco
  • SPARK框架下实现CPM(派系协同过滤算法)

    以下是我的Readme陈述算法思路,还没写完,先发上来,增加浏览量,之后部分我近几天补充。

    Donuts_choco
  • linux kernel Documentation filesystems overlayfs

    Please see MAINTAINERS file for where to send questions.

    heidsoft
  • 如何通过solc编译solidity编写的以太坊智能合约

    solidity编写的以太坊智能合约可通过命令行编译工具solc来进行编译,成为以太坊虚拟机中的代码。solc编译后最终部署到链上形成我们所见到的各种智能合约。

    笔阁
  • 在均匀电荷的纳米孔中,通过修饰的Dukhin数对1:1电解质进行选择性的缩放(CM MNP)

    栾博舒
  • C. NEKO's Maze Game

    time limit per test:1.5 seconds memory limit per test:256 megabytes inputstandar...

    某些人
  • RFC2616-HTTP1.1-Header Field Definitions(头字段规定部分—单词注释版)

    zaking
  • InfoGAN、GAN训练不稳定因素分析

    Many people have recommended me the infoGAN paper, but I hadn't taken the time t...

    用户1908973
  • Kosaraju算法

    SCC = strong connected component. 即强连通分量。

    Steve Wang

扫码关注云+社区

领取腾讯云代金券