Document Open Access Logo

Improved Approximation Bounds for the Minimum Constraint Removal Problem

Authors Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri, Kasturi Varadarajan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.2.pdf
  • Filesize: 0.81 MB
  • 19 pages

Document Identifiers

Author Details

Sayan Bandyapadhyay
  • Department of Computer Science, University of Iowa, Iowa City, USA
Neeraj Kumar
  • Department of Computer Science, University of California, Santa Barbara, USA
Subhash Suri
  • Department of Computer Science, University of California, Santa Barbara, USA
Kasturi Varadarajan
  • Department of Computer Science, University of Iowa, Iowa City, USA

Funding

Research of Sayan Bandyapadhyay, Neeraj Kumar and Subhash Suri was supported in part by the NSF grant CCF-1525817. Research of Sayan Bandyapadhyay and Kasturi Varadarajan was supported in part by the NSF grant CCF-1615845.

Cite As Get BibTex

Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri, and Kasturi Varadarajan. Improved Approximation Bounds for the Minimum Constraint Removal Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.2

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Minimum Constraint Removal
  • Minimum Color Path
  • Barrier Resilience
  • Obstacle Removal
  • Obstacle Free Path
  • Approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. Agarwal, N. Kumar, S. Sintos, and S. Suri. Computing shortest paths in the plane with removable obstacles. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), pages 5:1-5:15, 2018. Google Scholar
  2. H. Alt, S. Cabello, P. Giannopoulos, and C. Knauer. On some connection problems in straight-line segment arrangements. 27th EuroCG, pages 27-30, 2011. Google Scholar
  3. S. Bereg and D. G. Kirkpatrick. Approximating barrier resilience in wireless sensor networks. In 5th ALGOSENSORS 2009, pages 29-40, 2009. Google Scholar
  4. H. J. Broersma, X. Li, G. Woeginger, and S. Zhang. Paths and cycles in colored graphs. Australasian journal of combinatorics, 31(1):299-311, 2005. Google Scholar
  5. D. Y. C. Chan and D. G. Kirkpatrick. Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience. Theor. Comput. Sci., 553:74-90, 2014. Google Scholar
  6. T. M. Chan and E. Grant. Exact algorithms and apx-hardness results for geometric packing and covering problems. Computational Geometry, 47(2):112-124, 2014. Google Scholar
  7. K.L. Clarkson and P.W. Shor. Application of random sampling in computational geometry, II. Discrete & Computational Geometry, 4:387-421, 1989. Google Scholar
  8. I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014, pages 624-633, 2014. Google Scholar
  9. E. Eiben, J. Gemmell, I. Kanj, and A. Youngdahl. Improved results for minimum constraint removal. In Proceedings of AAAI, AAAI press, 2018. Google Scholar
  10. E. Eiben and I. Kanj. How to navigate through obstacles? CoRR, abs/1712.04043, 2017. URL: http://arxiv.org/abs/1712.04043.
  11. L. Erickson and S. LaValle. A simple, but np-hard, motion planning problem. In Proceedings of AAAI, AAAI press, 2013. Google Scholar
  12. M. R. Fellows, J. Guo, and I. Kanj. The parameterized complexity of some minimum label problems. Journal of Computer and System Sciences, 76(8):727-740, 2010. Google Scholar
  13. R. Hassin, J. Monnot, and D. Segev. Approximation algorithms and hardness results for labeled connectivity problems. J. Comb. Optim., 14(4):437-453, 2007. Google Scholar
  14. K. Hauser. The minimum constraint removal problem with three robotics applications. In Tenth Workshop on the Algorithmic Foundations of Robotics, WAFR 2012, pages 1-17, 2012. Google Scholar
  15. J. Hershberger, N. Kumar, and S. Suri. Shortest paths in the plane with obstacle violations. In 25th Annual European Symposium on Algorithms, (ESA 2017), pages 49:1-49:14, 2017. Google Scholar
  16. K. Kedem, R. Livne, J. Pach, and M. Sharir. On the union of jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete & Computational Geometry, 1:59-70, 1986. Google Scholar
  17. M. Korman, M. Löffler, R. I. Silveira, and D. Strash. On the complexity of barrier resilience for fat regions. In 9th ALGOSENSORS 2013, pages 201-216, 2013. Google Scholar
  18. S.Khot and O. Regev. Vertex cover might be hard to approximate to within 2-epsilon. Journal of Computer and System Sciences, 74(3):335-349, 2008. Google Scholar
  19. K-C. R. Tseng and D. G. Kirkpatrick. On barrier resilience of sensor networks. In 7th ALGOSENSORS 2011, pages 130-144, 2011. Google Scholar
  20. S. Yuan, S. Varma, and J. P. Jue. Minimum-color path problems for reliability in mesh networks. In 24th INFOCOM 2005, volume 4, pages 2658-2669. IEEE, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact