Efficient recovery from power outage

Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber

Research output: Contribution to journalConference articlepeer-review

57 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)574-582
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Efficient recovery from power outage'. Together they form a unique fingerprint.

Cite this