2026-08-15T23:36:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9406 2024-03-06T10:44:19Z ddc:004 open_access

Improved Approximation Bounds for the Minimum Constraint Removal Problem Bandyapadhyay, Sayan Kumar, Neeraj Suri, Subhash Varadarajan, Kasturi Minimum Constraint Removal Minimum Color Path Barrier Resilience Obstacle Removal Obstacle Free Path Approximation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bandyapadhyay and Neeraj Kumar and Subhash Suri and Kasturi Varadarajan 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.2 urn:nbn:de:0030-drops-94066 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.2 eng https://creativecommons.org/licenses/by/3.0/legalcode