Abstract
Let R denote a connected region inside a simple polygon, P. By building 1-dimensional barriers in P ∖ R, we want to separate from R part(s) of P of maximum area. 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 a certain linearity condition. For example, this condition is satisfied for barrier curves in general position, if any two barriers cross at most once.
Even for simple cases (e. g., P a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient ≈ 11.65 approximation algorithm for the firefighter problem. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider application. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from B must not cross.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Altshuler, Y., Bruckstein, A.M.: On Short Cuts or Fencing in Rectangular Strips. arXiv:1911.5920v1[cs.CG] (November 26, 2010)
Anshelevich, E., Chakrabarty, D., Hate, A., Swamy, C.: Approximability of the Firefighter Problem: Computing Cuts over Time. Algorithmica 62(1-2), 520–536 (2012), preliminary version in proc. ISAAC 2009
Bansal, N., Gupta, A., Krishnaswamy, R.: A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover. In: Proc. SODA, pp. 1539–1545 (2010)
Bansal, N., Pruhs, K.: The Geometry of Scheduling. In: FOCS 2010, pp. 407–414 (2010)
Barghi, A., Winkler, P.: Firefighting on a random geometric graph. Random Structures & Algorithms, doi:10.1002/rsa.20511 (first published online: June 27, 2013)
Cabello, S., Giannopoulos, P.: The Complexity of Separating Points in the Plane. In: Proc. 29th ACM Symposium on Computational Geometry, pp. 379–386 (2013)
Cai, L., Verbin, E., Yang, L.: Firefighting on Trees (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 258–269. Springer, Heidelberg (2008)
Chekuri, C., Vondrák, R., Zenklusen, R.: Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. Prel. version in STOC 2011, 783–792 (2011), Revised version in http://arxiv.org/pdf/1105.4593v3.pdf (July 30, 2012)
Cohen, R., Katzir, L.: The Generalized Maximum Coverage Problem. Information Processing Letters 108, 15–22 (2008)
Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)
Finbow, S., King, A., MacGillivray, G., Rizzi, R.: The firefighter problem for graphs of maximum degree three. Discrete Mathematics 307(16), 2094–2105 (2007)
Finbow, S., MacGillivray, G.: The Firefighter Problem: a survey of results, directions and questions. Australasian J. Comb. 43, 57–78 (2009)
Floderus, P., Lingas, A., Persson, M.: Towards more efficient infection and fire fighting. Int. J. Found. Comput. Sci. 24(1), 3–14 (2013), preliminary version in proc. CATS 2011
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-completeness. W.H. Freeman and Company, New York (1979)
Ghaderi, R., Esnaashari, M., Meybodi, M.R.: An Adaptive Scheduling Algorithm for Set Cover Problem in Wireless Sensor Networks: A Cellular Learning Automata Approach. International Journal of Machine Learning and Computing 2(5) (October 2012)
Hassin, R., Levin, A.: An Approximation Algorithm for the Minimum Latency Set Cover Problem. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 726–733. Springer, Heidelberg (2005)
Khuller, S., Moss, A., Naor, J.S.: The budgeted maximum coverage problem. Information Processing Letters 70, 39–45 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Klein, R., Levcopoulos, C., Lingas, A. (2014). Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems. In: Pardo, A., Viola, A. (eds) LATIN 2014: Theoretical Informatics. LATIN 2014. Lecture Notes in Computer Science, vol 8392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54423-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-54423-1_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54422-4
Online ISBN: 978-3-642-54423-1
eBook Packages: Computer ScienceComputer Science (R0)