| Accession number;00A0399703 |
| Title;Algorithm Engineering: Surveys. Approximation Algorithms for Submodular Set Cover with Applications. |
| Author;FUJITO T(Nagoya Univ., Nagoya-shi, Jpn) |
Journal Title;IEICE Trans Inf Syst (Inst Electron Inf Commun Eng)
|
Journal Code:L1371A
|
ISSN:0916-8532
|
|
VOL.E83-D;NO.3;PAGE.480-487(2000)
|
| Figure&Table&Reference;REF.35 |
| Pub. Country;Japan |
| Language;English |
| Abstract;The main problem considered is submodular set cover, the problem of minimizing a linear function under a non-decreasing submodular constraint, which generalizes both wellknown set cover and minimum matroid base problems. The problem is NP-hard, and two natural greedy heuristics are introduced along with analysis of their performance. As applications of these heuristics we consider various special cases of submodular set cover, including partial cover variants of set cover and vertex cover, and node-deletion problems for hereditary and matroidal properties. An approximation bound derived for each of them is either matching or generalizing the best existing bounds. (author abst.) |
