An approximation algorithm for submodular hitting set problem with linear penalties

DOI10.1007/s10878-020-00653-6zbMath1467.90052OpenAlexW3088443916MaRDI QIDQ830939

N. E. Zubov

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

zbMATH Keywords

approximation algorithmsubmodularpenaltyprimal-dualhitting set

Mathematics Subject Classification ID

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