Approximation algorithms for the submodular edge cover problem with submodular penalties (Q2031056)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Approximation algorithms for the submodular edge cover problem with submodular penalties |
scientific article; zbMATH DE number 7356478
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Approximation algorithms for the submodular edge cover problem with submodular penalties |
scientific article; zbMATH DE number 7356478 |
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
