{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:07:12Z","timestamp":1750306032110,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,12,7]],"date-time":"2018-12-07T00:00:00Z","timestamp":1544140800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EU grant FP7-PEOPLE-2012-ITN","award":["316647"],"award-info":[{"award-number":["316647"]}]},{"name":"Seed Project \u201cRisk Protection in Complex Networks\u201d of ETH Zurich Risk Center"},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021_165866"],"award-info":[{"award-number":["200021_165866"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"\u201cNew Approaches to Constrained Submodular Maximization.\u201d"},{"name":"\u201cMixed-Integer Nonlinear Optimization.\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most-studied graph structures in this context and the focus of this article. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step\n            <jats:italic>B<\/jats:italic>\n            many non-burning vertices can be protected from catching fire. The Firefighter problem asks, for a given\n            <jats:italic>B<\/jats:italic>\n            , to maximize the number of vertices that will not catch fire, whereas RMFC (on a tree) asks to find the smallest\n            <jats:italic>B<\/jats:italic>\n            that allows for saving all leaves of the tree. Prior to this work, the best known approximation ratios were an\n            <jats:italic>O<\/jats:italic>\n            (1)-approximation for the Firefighter problem and an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-approximation for RMFC, both being LP-based and essentially matching the integrality gaps of two natural LP relaxations.\n          <\/jats:p>\n          <jats:p>\n            We improve on both approximations by presenting a PTAS for the Firefighter problem and an\n            <jats:italic>O<\/jats:italic>\n            (1)-approximation for RMFC, both qualitatively matching the known hardness results. Our results are obtained through a combination of the known LPs with several new techniques, which allow for efficiently enumerating over super-constant size sets of constraints to strengthen the natural LPs.\n          <\/jats:p>","DOI":"10.1145\/3173046","type":"journal-article","created":{"date-parts":[[2018,12,7]],"date-time":"2018-12-07T13:17:29Z","timestamp":1544188649000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Firefighting on Trees Beyond Integrality Gaps"],"prefix":"10.1145","volume":"15","author":[{"given":"David","family":"Adjiashvili","sequence":"first","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Baggio","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7148-9304","authenticated-orcid":false,"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,7]]},"reference":[{"volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Adjiashvili D.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9469-y"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.03.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_66"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.11.011"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791130"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_25"},{"key":"e_1_2_1_8_1","first-page":"1814","article-title":"The surviving rate of a graph for the firefighter problem","volume":"23","author":"Cai L.","year":"2009","journal-title":"SIAM J. Discrete Math."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP\u201916)","author":"Chakrabarty D.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Chalermsook P.","key":"e_1_2_1_11_1"},{"volume-title":"Proceedings of the 14th International Workshop on Approximation and Online Algorithms (WAOA\u201917)","author":"Chalermsook P.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the International Workshop an Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201904)","author":"Chekuri C.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082038"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.04.008"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28050-4_2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118792.3119294"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21673"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.053"},{"key":"e_1_2_1_21_1","first-page":"57","article-title":"The firefighter problem: a survey of results, directions and questions","volume":"43","author":"Finbow S.","year":"2009","journal-title":"Austral. J. Combin."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113400017"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30347-0_19"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.06.002"},{"key":"e_1_2_1_25_1","first-page":"179","article-title":"Attempting to narrow the integrality gap for the firefighter problem on trees","volume":"70","author":"Hartke S. G.","year":"2006","journal-title":"Discr. Methods Epidemiol."},{"volume-title":"Proceedings of the 24th Manitoba Conference on Combinatorial Mathematics and Computing.","year":"1995","author":"Hartnell B.","key":"e_1_2_1_26_1"},{"volume":"145","volume-title":"Proceedings of Congressus Numerantium","author":"Hartnell B.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.E94.D.196"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2009.05.007"},{"volume-title":"Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN\u201914)","author":"Klein R.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2014.06.018"},{"key":"e_1_2_1_32_1","first-page":"83","article-title":"On the firefighter problem","volume":"47","author":"MacGillivray G.","year":"2013","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/120876113"},{"volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","year":"2003","author":"Schrijver A.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3173046","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3173046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:50Z","timestamp":1750215770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3173046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,7]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3173046"],"URL":"https:\/\/doi.org\/10.1145\/3173046","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,12,7]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}