Approximation algorithms for the submodular edge cover problem with submodular penalties (Q2031056)

In an undirected graph with edge set \(E\), edge covers are discussed. Edge sets have positive values attached via a submodular set function. To find a minimum cover is then NP-hard and needs an approximation algorithm. The authors study this problem in an extended, respectively modified, version, show such an algorithm, given verbally, and provide proofs with up to 25 \(\Sigma\)-symbols per page. The bibliography contains 16 entries.