Approximation Algorithms for Submodular Set Cover with Applications

Toshihiro FUJITO

Approximation Algorithms for Submodular Set Cover with Applications

Toshihiro FUJITO

Full Text Views

0

Cite this

Summary :

The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known 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.

Publication: IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.480-487

Publication Date: 2000/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: INVITED SURVEY PAPER

Category: Approximate Algorithms for Combinatorial Problems

Cite this

Copy

Toshihiro FUJITO, "Approximation Algorithms for Submodular Set Cover with Applications" in IEICE TRANSACTIONS on Information, vol. E83-D, no. 3, pp. 480-487, March 2000, doi: .
Abstract: The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_480/_p

Copy

@ARTICLE{e83-d_3_480,
author={Toshihiro FUJITO, },
journal={IEICE TRANSACTIONS on Information},
title={Approximation Algorithms for Submodular Set Cover with Applications},
year={2000},
volume={E83-D},
number={3},
pages={480-487},
abstract={The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known 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.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Approximation Algorithms for Submodular Set Cover with Applications
T2 - IEICE TRANSACTIONS on Information
SP - 480
EP - 487
AU - Toshihiro FUJITO
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known 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.
ER -