通用最小曼哈顿网络问题的动态编程方法（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