Randomized approximation of bounded multicovering problems
From MaRDI portal
Publication:679446
DOI10.1007/BF02523687zbMath0873.68077MaRDI QIDQ679446
Gideon Schechtman, Avishai Wool, David Peleg
Publication date: 29 October 1997
Published in: Algorithmica (Search for Journal in Brave)
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
