Randomized approximation for the set multicover problem in hypergraphs
type: Item
instance of: scholarly article
title: Randomized approximation for the set multicover problem in hypergraphs
zbMATH Open document ID: 1336.68293
author: Mourad El Ouali
author: Peter Munstermann
author: Anand Srivastav
published in: Algorithmica
publication date: 2016-03-29T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6560719
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: approximation algorithms
zbMATH Keywords: randomized algorithm
zbMATH Keywords: hypergraphs
zbMATH Keywords: set cover
zbMATH Keywords: set multicover
MaRDI profile type: Publication
full work available at URL: s00453-014-9962-9
OpenAlex ID: W2075631357
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Using homogeneous weights for approximating the partial cover problem
cites work: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: An approximation algorithm for the partial vertex cover problem in hypergraphs
cites work: A randomised approximation algorithm for the hitting set problem
cites work: Approximation algorithms for maximization problems arising in graph partitioning
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Approximation algorithms for partial covering problems
cites work: Probabilistic methods for algorithmic discrete mathematics
cites work: A fast approximation algorithm for the multicovering problem
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: Approximation Algorithms for the Set Covering and Vertex Cover Problems
cites work: Improved approximation algorithms for maximum graph partitioning problems
cites work: Approximation algorithms for combinatorial problems
cites work: Approximate Set Covering in Uniform Hypergraphs
cites work: On the ratio of optimal integral and fractional covers
cites work: Randomized approximation of bounded multicovering problems
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
DOI: 10.1007/S00453-014-9962-9
description: scientific article; zbMATH DE number 6560719