An approximation algorithm for submodular hitting set problem with linear penalties
From MaRDI portal
Publication:830939
DOI10.1007/s10878-020-00653-6zbMath1467.90052OpenAlexW3088443916MaRDI QIDQ830939
Publication date: 10 May 2021
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-020-00653-6
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- Unnamed Item
- Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
- A randomised approximation algorithm for the hitting set problem
- Improved approximation algorithms for the facility location problems with linear/submodular penalties
- \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
- Practical and efficient algorithms for the geometric hitting set problem
- A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
- On approximation of the vertex cover problem in hypergraphs
- The primal-dual method for approximation algorithms
- A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties
- A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
- Greedy approximations for minimum submodular cover with submodular cost
- A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
- Submodular functions and optimization.
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Approximate Set Covering in Uniform Hypergraphs
- Hitting Set for hypergraphs of low VC-dimension
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Submodular Function Minimization under Covering Constraints
- Foundations of Information and Knowledge Systems
This page was built for publication: An approximation algorithm for submodular hitting set problem with linear penalties
