Randomized approximation of bounded multicovering problems

DOI10.1007/BF02523687zbMath0873.68077MaRDI QIDQ679446

Gideon Schechtman, Avishai Wool, David Peleg

Publication date: 29 October 1997

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

vertex cover problembounded set cover problemmulticovering problems

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items

Siting renewable power generation assets with combinatorial optimisation ⋮ An effective and simple heuristic for the set covering problem ⋮ Approximation of set multi-cover via hypergraph matching ⋮ Admission control with advance reservations in simple networks ⋮ Approximation algorithm for the multicovering problem ⋮ An approximation algorithm for the partial vertex cover problem in hypergraphs ⋮ A randomised approximation algorithm for the hitting set problem ⋮ Computational experience with approximation algorithms for the set covering problem ⋮ Exact multi-covering problems with geometric sets ⋮ Randomized approximation for the set multicover problem in hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Efficient bounds for the stable set, vertex cover and set packing problems
• A fast approximation algorithm for the multicovering problem
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Computational experience with approximation algorithms for the set covering problem
• An analysis of the greedy algorithm for the submodular set covering problem
• On the Fractional Solution to the Set Covering Problem
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Vertex packings: Structural properties and algorithms
• How to Allocate Network Centers
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations