Efficient recovery from power outage

We study problems that are motivated by a real-life problem of efficient recovery from a wide scale electric power outage caused by a major disaster such as a hurricane or an equipment failure. In most of these cases an optimized scheduling of the workforce is required, since the work crews on hand cannot handle the immediate recovery of the whole network. We model two variants of this problem: the budgeted problem, and the minimum weighted latency problem. We consider the problems for the general case as well as for two special cases: trees, and bipartite networks. All, but one of the problems (the budgeted tree problem), are NP-Hard and the algorithms given for them are approximation algorithms. For the budgeted tree problem we give an optimal solution. Interestingly, the budgeted problem for bipartite networks is exactly the budgeted maximum set cover problem, for which we give the best ratio approximation algorithm.