FLOOD - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CHALLENGE

EXPLANATION

This problem can be seen as an instance of the Node Weighted Steiner Tree problem in a grid graph. It is proven that in general graphs, no approximation algorithm can guarantee an approximation ratio that is asymptotically better than log n. However, we do have c log n approximation algorithm for some fixed constant c, for example a 2 log n approximation algorithm exists. An even stronger result is available. That is, there exists some constance for which no c log n approximation algorithm exists, unless P=NP [1]. The same result probably also holds in a grid graph too. However, there may also be better approximation algorithms for grid graphs.

Nonetheless, the 2 logn approximation algorithm is not time efficient enough for our problem. So we need to resolve to other heuristics. Here we present an approximation algorithm by Zac:

  • Let all the cells be nodes in a graph
  • For each cell/node, add edges to the surrounding (up to) eight cells/nodes
  • For each edge, set the weight of this edge to be the sum of the weights of the endpoint cells (an island has weight 0)
  • From now on, ignore the node weights and consider only the edge weights
  • Find a minimum spanning tree of this graph
  • Iteratively prune all leaves until only islands are leaves
  • Each non-island node remaining in this tree is to be used in the final solution

Of course, there are other tricks (e.g. local search improvements) that one can employ to try to improve this solution. The solution is valid since the sub-tree we find is connected and spans all islands. The weights of the edges are supposed to somehow capture the cost of using the endpoints in the final solution. Of course, this is not a great approximation as there are some bad examples exist. However, it did work fairly well on the randomly generated instances.

References
[1] Philip N. Klein, R. Ravi: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. J. Algorithms 19(1): 104-115 (1995)
If you would like to see how the final verion of the editorial for ‘FLOOD’ was created check out the following conversation at Zac and Duc’s conversation on Flood