Online Firefighting on Trees

Coupechoux, P, Demange, M, Ellison, D and Jouve, B 2018, 'Online Firefighting on Trees', in Jon Lee et al (ed.) Lecture Notes in Computer Science, vol 10856, Marrakesh, Morocco, April 11-13 2018, pp. 121-132.


Document type: Conference Paper
Collection: Conference Papers

Title Online Firefighting on Trees
Author(s) Coupechoux, P
Demange, M
Ellison, D
Jouve, B
Year 2018
Conference name 5th International Symposium on Combinatorial Optimization, ISCO 2018
Conference location Marrakesh, Morocco
Conference dates April 11-13 2018
Proceedings title Lecture Notes in Computer Science, vol 10856
Editor(s) Jon Lee et al
Publisher Springer International Publishing
Place of publication Cham, Switzerland
Start page 121
End page 132
Total pages 12
Abstract In the Firefighter problem, introduced by Hartnell in 1995, a fire spreads through a graph while a player chooses which vertices to protect in order to contain it. In this paper, we focus on the case of trees and we consider as well the Fractional Firefighter game where the amount of protection allocated to a vertex lies between 0 and 1. We introduce the online version of both Firefighter and Fractional Firefighter, in which the number of firefighters available at each turn is revealed over time. We show that the greedy algorithm on finite trees, which maximises at each turn the amount of vertices protected, is 1/2-competitive for both online versions; this was previously known only in special cases of Firefighter. We also show that, for Firefighter, the optimal competitive ratio of online algorithms ranges between 1/2 and the inverse of the golden ratio. The greedy algorithm is optimal if the number of firefighters is not bounded and we propose an optimal online algorithm which reaches the inverse of the golden ratio if at most 2 firefighters are available. Finally, we show that on infinite trees with linear growth, any firefighter sequence stronger than a non-zero periodic sequence is sufficient to contain the fire, even when revealed online.
Subjects Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
Operations Research
Analysis of Algorithms and Complexity
Keyword(s) Firefighter problem
online optimisation
graph algorithms
tree
DOI - identifier 10.1007/978-3-319-96151-4_11
Copyright notice ©
ISBN 9783319961507
Versions
Version Filter Type
Altmetric details:
Access Statistics: 16 Abstract Views  -  Detailed Statistics
Created: Thu, 06 Dec 2018, 10:39:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us