Approximation algorithms for the submodular edge cover problem with submodular penalties (Q2031056)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximation algorithms for the submodular edge cover problem with submodular penalties |
scientific article |
Statements
Approximation algorithms for the submodular edge cover problem with submodular penalties (English)
0 references
8 June 2021
0 references
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.
0 references
edge cover
0 references
set cover
0 references
submodular function
0 references
penalty
0 references
primal-dual
0 references
0 references
0 references
0 references