A 3-2/b(G)-approximation algorithm for the graph burning problem

The graph burning problem is an NP-Hard optimization problem that models the sequential spread of information over a network. Due to its nature, this problem has been approached through approximation algorithms and heuristics. This paper introduces a new 3-2/b(G)-approximation algorithm for the graph burning problem over general graphs, where b(G) is the size of an optimal solution. This algorithm, named 'burning greedy permutation' algorithm, is based on greedy permutations and is easy to implement. According to a brief empirical analysis, the proposed algorithm generates competitive solutions, some of which are better than the best previously known.