文章基本信息

标题：Improved Approximation Bounds for the Minimum Constraint Removal Problem
本地全文：下载
作者：Sayan Bandyapadhyay ; Neeraj Kumar ; Subhash Suri 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：116
页码：1-19
DOI：10.4230/LIPIcs.APPROX-RANDOM.2018.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In the minimum constraint removal problem, we are given a set of 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 (perhaps surprisingly) no sub-linear approximations are known even for simple obstacles such as rectangles and disks. The main result of our paper is a new approximation technique that gives O(sqrt{n})-approximation for rectangles, disks as well as rectilinear polygons. The technique also gives O(sqrt{n})-approximation for the minimum color path problem in graphs. We also present some inapproximability results for the geometric constraint removal problem.
关键词：Minimum Constraint Removal; Minimum Color Path; Barrier Resilience; Obstacle Removal; Obstacle Free Path; Approximation