An approximation algorithm for submodular hitting set problem with linear penalties
type: Item
instance of: scholarly article
title: An approximation algorithm for submodular hitting set problem with linear penalties
zbMATH Open document ID: 1467.90052
author: N. E. Zubov
published in: Journal of Combinatorial Optimization
publication date: 2021-05-10T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7346752
zbMATH Keywords: hitting set
zbMATH Keywords: submodular
zbMATH Keywords: penalty
zbMATH Keywords: approximation algorithm
zbMATH Keywords: primal-dual
MaRDI profile type: Publication
full work available at URL: s10878-020-00653-6
OpenAlex ID: W3088443916
cites work: Hitting Set for hypergraphs of low VC-dimension
cites work: Practical and efficient algorithms for the geometric hitting set problem
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
cites work: Submodular functions and optimization.
cites work: Foundations of Information and Knowledge Systems
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
cites work: Submodular Function Minimization under Covering Constraints
cites work: Approximate Set Covering in Uniform Hypergraphs
cites work: A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties
cites work: A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
cites work: Improved approximation algorithms for the facility location problems with linear/submodular penalties
cites work: \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
cites work: On approximation of the vertex cover problem in hypergraphs
cites work: A randomised approximation algorithm for the hitting set problem
cites work: Q3910298
cites work: Greedy approximations for minimum submodular cover with submodular cost
cites work: The primal-dual method for approximation algorithms
cites work: Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
DOI: 10.1007/S10878-020-00653-6
description: scientific article; zbMATH DE number 7346752