Improved approximation bounds for the minimum constraint removal problem
Improved approximation bounds for the minimum constraint removal problem
复制标题
改进了最小约束去除问题的近似界限
DOI：
10.1016/j.comgeo.2020.101650
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Varadarajan, K.
中科院分区：
文献类型：
--
作者：
Bandyapadhyay, S;Kumar, N;Suri, S;Varadarajan, K.
在最小约束去除问题中，我们给定一组重叠的几何物体作为平面上的障碍物，我们想要找到从源点s通过无障碍路径到达目标点t所必须去除的最小障碍物数量。众所周知，这个问题是难以解决的，即使对于简单的障碍物，如矩形和圆盘，也没有已知的亚线性近似。本文的主要结果是一个近似框架，它给出了多边形障碍物的O (n α (n))-近似，其中α (n)表示逆Ackermann函数。对于伪圆盘和直线多边形，同样的技术可以实现O (n)-近似。该技术还给出了图中最小颜色路径问题的O (n)逼近。我们也给出了几何约束去除问题的一些不逼近性结果。
In the minimum constraint removal problem, we are given a set of overlapping geometric objects as obstacles in the plane, and we want to find the minimum number of obstacles that must be removed to reach a target point t from the source point s by an obstacle-free path. The problem is known to be intractable and no sub-linear approximations are known even for simple obstacles such as rectangles and disks. The main result of our paper is an approximation framework that gives an O (n α (n))-approximation for polygonal obstacles, where α (n) denotes the inverse Ackermann's function. For pseudodisks and rectilinear polygons, the same technique achieves an O (n)-approximation. The technique also gives O (n)-approximation for the minimum color path problem in graphs. We also present some inapproximability results for the geometric constraint removal problem.