Approximation algorithms for the submodular edge cover problem with submodular penalties

DOI10.1016/J.TCS.2021.04.017OpenAlexW3158464247MaRDI QIDQ2031056

Yanyan Li

Publication date: 8 June 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.04.017

zbMATH Keywords

submodular functionedge coverset coverpenaltyprimal-dual

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
• Design and analysis of approximation algorithms
• A note on submodular function minimization with covering type linear constraints
• A note on the submodular vertex cover problem with submodular penalties
• Constrained weighted matchings and edge coverings in graphs
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A note of vertex arboricity of planar graphs without 4-cycles intersecting with 6-cycles
• Submodular functions and optimization.
• Prize-Collecting Steiner Network Problems
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Submodular Function Minimization under Covering Constraints
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

This page was built for publication: Approximation algorithms for the submodular edge cover problem with submodular penalties