Approximation Algorithms for Submodular Set Cover with Applications(Special Issue on Algorithm Engineering : Surveys)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2000-03-25

著者

• Fujito Toshihiro

  The Department Of Electronics Nagoya University

関連論文

• On the Legal Firing Sequence Problem of Petri Nets with Cactus Structure (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
• Approximation Algorithms for Submodular Set Cover with Applications(Special Issue on Algorithm Engineering : Surveys)

スポンサーリンク