专栏首页arxiv.org翻译专栏通用最小曼哈顿网络问题的动态编程方法(CS DS)
原创

通用最小曼哈顿网络问题的动态编程方法(CS DS)

我们研究广义最小曼哈顿网络(GMMN)问题:给定一个由欧几里得平面 R^2 中两个点配对组成的集合 P,要求我们找到一个最小长度的几何网络,该网络由轴对齐的线段组成,并为 P 中的每一对线段都包含一条 L_1 公制中的最短路径(所谓的曼哈顿路径)。这个问题通常是对几个 NP-hard 的网络设计问题的一般概括,这些问题都接受常数因子近似算法,如直线 Steiner arborescence (RSA) 问题,GMMN 问题是否也是如此,还有待商榷。作为一种自下而上的探索,Schnizler(2015)将研究重点放在了 P 中两点配对定义的矩形的交点图上,并给出了一种针对 GMMN 问题的多项式时间动态编程算法,其输入受限,使其交点图的树宽和最大度数都由常数约束。在本文中,作为首次尝试去掉度数约束的尝试,我们提供了一种星形情况下的多项式时间算法,并基于改进的动态编程方法将其扩展到一般树形情况下。

原文题目:Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem

原文:We study the generalized minimum Manhattan network (GMMN) problem: given a set ​ of pairs of two points in the Euclidean plane ​, we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the ​ metric (a so-called Manhattan path) for each pair in ​. This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in ​, and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach.

原文作者:Yuya Masumura, Taihei Oki, Yutaro Yamaguchi

原文地址:https://arxiv.org/abs/2004.11166

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一种用于语音情感识别中转移学习的改良距离损失的连体神经网络(CS CV)

    自动情感识别在人机交互过程和物联网技术设计中发挥着重要作用。然而,情感识别系统的一个普遍问题在于可靠标签的稀缺。通过对感兴趣的样本之间的成对差异进行建模,连体网...

    刘持诚
  • 监督领域自适应:我们一直都在做图形嵌入吗?(CS LG)

    当训练数据和测试数据的分布不同时,机器学习模型的性能往往会受到影响。领域自适应就是缩小数据集之间分布差距的过程。在本文中,我们展示了现有的领域适配方法可以被表述...

    刘持诚
  • 异步 Q-Learning 的样本复杂度:更敏锐的分析和方差减少技术(CS LG)

    异步 Q-learning 的目的是基于行为策略诱导的马尔科夫样本的单一轨迹,学习马尔科夫决策过程(MDP)的最优行动值函数(或Q-function)。专注于一...

    刘持诚
  • Codeforces 839B Game of the Rows【贪心】

    B. Game of the Rows time limit per test:1 second memory limit per test:256 megab...

    Angel_Kitty
  • SPINNING单车你需要知道的一些事(一)单车怎么调整

    • If toe cages and straps are used, be sure to align the ball of your foot over ...

    小飞侠xp
  • CNCF大使档案:TiKV的Queeny Jin

    Our first ambassador spotlight goes to Queeny Jin, who has been spreading the wo...

    CNCF
  • Android NDK Debug

    前言:说真的Android NDK debug还是推荐lldb,gdb经常莫名其妙的不成功。不过下面的这个流程是谷歌官方建议的,还是有参考价值的。尤其是在App...

    望天
  • Kubernetes Scheduler原理解析

    本文是对Kubernetes Scheduler的算法解读和原理解析,重点介绍了预选(Predicates)和优选(Priorities)步骤的原理,并介绍了默...

    Walton
  • 【ZooKeeper系列】2.用Java实现ZooKeeper API的调用

    在前一篇我们介绍了ZooKeeper单机版、伪集群和集群环境搭建,通过命令行的方式做了节点的创建、删除、更新、获取节点信息的测试。Zookeeper 的目的是为...

    猿人谷
  • SAP CRM One Order里Complex Set的一个例子:Partner Set

    CRMT_PARTNER_EXT has nothing to do with the distinction into internal and extern...

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券