Dynamic Maintenance of Approximate Solutions of Min-Weighted Node Cover and Min-Weighted Set Cover Problems

TitleDynamic Maintenance of Approximate Solutions of Min-Weighted Node Cover and Min-Weighted Set Cover Problems
Publication TypeTechnical Report
Year of Publication1993
AuthorsGambosi, G., Protasi M., & Talamo M.
Other Numbers839
Abstract

In this paper, we introduce new algorithms for the dynamic maintenance of approximated solutions of Min-Weighted Node Cover and Min-Weighted Set Cover. For what concerns Min-Weighted Node Cover, for any sequence of edge insertions and deletions, the algorithms maintain a solution whose approximation ratio (that is, the ratio between the approximate and the optimum value) is equal to the best asymptotic one for the static case. The algorithms require O(1) time for edge insertion, while an O(1) amortized time is required for edge deletion.For what regards Min-Weighted Set Cover, we present dynamic algorithms whose approximation ratio matches one of the two different and incomparable best approximate bounds for the static case. The time complexity for element insertion and its amortized complexity for element deletion are proportional to the maximum redundancy of an element in the approximate solution.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-051.pdf
Bibliographic Notes

ICSI Technical Report TR-93-051

Abbreviated Authors

G. Gambosi, M. Protasi, and M. Talamo

ICSI Publication Type

Technical Report