{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T20:36:05Z","timestamp":1774730165713,"version":"3.50.1"},"reference-count":20,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T00:00:00Z","timestamp":1523404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DACH project","award":["Kl 655\/19"],"award-info":[{"award-number":["Kl 655\/19"]}]},{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"publisher","award":["2017-03750"],"award-info":[{"award-number":["2017-03750"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in P \\ R , we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set B that satisfies certain conditions. Even for simple cases (e.g., P is a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient \u224811.65 approximation algorithm for the firefighter problem, where the set B of allowed barriers is any set of straight-line segments with all endpoints on the boundary of P and pairwise disjoint interiors. Since this algorithm solves a much more general problem\u2014a hybrid of scheduling and maximum coverage\u2014it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross.<\/jats:p>","DOI":"10.3390\/a11040045","type":"journal-article","created":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T12:16:50Z","timestamp":1523449010000},"page":"45","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems"],"prefix":"10.3390","volume":"11","author":[{"given":"Rolf","family":"Klein","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik I, Universit\u00e4t Bonn, D-53117 Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, 221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, 221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,4,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1007\/s00453-010-9469-y","article-title":"Approximability of the Firefighter Problem: Computing Cuts over Time","volume":"62","author":"Anshelevich","year":"2012","journal-title":"Algorithmica"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Cai, L., Verbin, E., and Yang, L. (2008, January 15\u201317). Firefighting on Trees: (1-1\/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm. Proceedings of the 19th International Symposium ISAAC 2008, LNCS 5369, Gold Coast, Australia.","DOI":"10.1007\/978-3-540-92182-0_25"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2094","DOI":"10.1016\/j.disc.2005.12.053","article-title":"The firefighter problem for graphs of maximum degree three","volume":"307","author":"Finbow","year":"2007","journal-title":"Discret. Math."},{"key":"ref_4","unstructured":"Floderus, P., Lingas, A., and Persson, M. (2011, January 17\u201320). Towards more efficient infection and fire fighting. Proceedings of the Computing: The Australasian Theory Symposium (CATS 2011), CRPIT 119, Perth, Australia."},{"key":"ref_5","first-page":"57","article-title":"The Firefighter Problem: A survey of results, directions and questions","volume":"43","author":"Finbow","year":"2009","journal-title":"Australas. J. Comb."},{"key":"ref_6","first-page":"261","article-title":"Approximation algorithms for the geometric firefighter and budget fence problems","volume":"Volume 8392","author":"Klein","year":"2014","journal-title":"Lecture Notes in Computer Science, Proceedings of the 11th Latin American Symposium in Theoretical Informatics (LATIN 2014), Montevideo, Uruguay, 31 March\u20134 April 2014"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of ln n for approximating set cover","volume":"45","author":"Feige","year":"1998","journal-title":"J. ACM"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1002\/rsa.20511","article-title":"Firefighting on a random geometric graph","volume":"46","author":"Barghi","year":"2013","journal-title":"Random Struct. Algorithms"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","article-title":"The budgeted maximum coverage problem","volume":"70","author":"Khuller","year":"1999","journal-title":"Inf. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.ipl.2008.03.017","article-title":"The Generalized Maximum Coverage Problem","volume":"108","author":"Cohen","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bansal, N., Gupta, A., and Krishnaswamy, R. (2010, January 17\u201319). A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover. Proceedings of the Twenty-First Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), Austin, TX, USA.","DOI":"10.1137\/1.9781611973075.125"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bansal, N., and Pruhs, K. (2010, January 23\u201326). The Geometry of Scheduling. Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.46"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Hassin, R., and Levin, A. (2005, January 3\u20136). An Approximation Algorithm for the Minimum Latency Set Cover Problem. Proceedings of the 13th Annual European Symposium on Algorithms (ESA), Mallorca, Spain.","DOI":"10.1007\/11561071_64"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"626","DOI":"10.7763\/IJMLC.2012.V2.203","article-title":"An Adaptive Scheduling Algorithm for Set Cover Problem in Wireless Sensor Networks: A Cellular Learning Automata Approach","volume":"2","author":"Ghaderi","year":"2012","journal-title":"Int. J. Mach. Learn. Comput."},{"key":"ref_15","unstructured":"Chekuri, C., Vondr\u00e1k, R., and Zenklusen, R. (2011, January 6\u20138). Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. Proceedings of the STOC\u201911 43rd ACM Symposium on Theory of Computing, San Jose, CA, USA. Available online: http:\/\/arxiv.org\/pdf\/1105.4593v3.pdf."},{"key":"ref_16","unstructured":"Klein, R., Langetepe, E., Levcopoulos, C., Lingas, A., and Schwarzwald, B. (2015, January 22\u201325). On a Fire Fighter\u2019s Problem. Proceedings of the 31st International Symposium on Computational Geometry (SoCG 2015), Eindhoven, The Netherlands."},{"key":"ref_17","unstructured":"Zambon, M.J.O., de Rezende, P.J., and de Souza, C.C. (2016, January 3\u20135). Exact Solutions for the Geometric Firefighter Problem. Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG), Vancouver, BC, Canada."},{"key":"ref_18","unstructured":"Altshuler, Y., and Bruckstein, A.M. (arXiv, 2010). On Short Cuts or Fencing in Rectangular Strips, arXiv."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cabello, S., and Giannopoulos, P. (2013, January 17\u201320). The Complexity of Separating Points in the Plane. Proceedings of the 29th ACM Symposium on Computational Geometry, Rio de Janeiro, Brazil.","DOI":"10.1145\/2493132.2462383"},{"key":"ref_20","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness, W.H. Freeman and Company."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/45\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:00:22Z","timestamp":1760194822000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,11]]},"references-count":20,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,4]]}},"alternative-id":["a11040045"],"URL":"https:\/\/doi.org\/10.3390\/a11040045","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,11]]}}}