Approximation algorithms for the submodular edge cover problem with submodular penalties
type: Item
instance of: scholarly article
title: Approximation algorithms for the submodular edge cover problem with submodular penalties
author: Yanyan Li
published in: Theoretical Computer Science
publication date: 2021-06-08T00:00:00Z
review text: 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.
reviewed by: Gunther Schmidt
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7356478
zbMATH Keywords: edge cover
zbMATH Keywords: set cover
zbMATH Keywords: submodular function
zbMATH Keywords: penalty
zbMATH Keywords: primal-dual
MaRDI profile type: Publication
full work available at URL: j.tcs.2021.04.017
OpenAlex ID: W3158464247
cites work: A note of vertex arboricity of planar graphs without 4-cycles intersecting with 6-cycles
cites work: Design and analysis of approximation algorithms
cites work: Q4414632
cites work: Q5592646
cites work: A push-relabel framework for submodular function minimization and applications to parametric optimization
cites work: Submodular functions and optimization.
cites work: Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
cites work: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
cites work: Prize-Collecting Steiner Network Problems
cites work: Submodular Function Minimization under Covering Constraints
cites work: A note on submodular function minimization with covering type linear constraints
cites work: A note on the submodular vertex cover problem with submodular penalties
cites work: Constrained weighted matchings and edge coverings in graphs
cites work: Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
DOI: 10.1016/J.TCS.2021.04.017
description: scientific article; zbMATH DE number 7356478