Randomized approximation of bounded multicovering problems
From MaRDI portal
Publication:679446
DOI10.1007/BF02523687zbMATH Open0873.68077MaRDI QIDQ679446FDOQ679446
Gideon Schechtman, Avishai Wool, David Peleg
Publication date: 29 October 1997
Published in: Algorithmica (Search for Journal in Brave)
Recommendations
- Randomized approximation for the set multicover problem in hypergraphs
- Approximation algorithm for the multicovering problem
- Tight approximation bounds for maximum multi-coverage
- Tight approximation bounds for maximum multi-coverage
- scientific article; zbMATH DE number 2077129
- Approximability and parameterized complexity of multicover by \(c\)-intervals
- Approximation algorithm for the stochastic prize-collecting set multicover problem
- A fast approximation algorithm for the multicovering problem
- Bicriteria approximation of chance-constrained covering problems
- Revisiting the approximation bound for stochastic submodular cover
Cites Work
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Optimization, approximation, and complexity classes
- A fast approximation algorithm for the multicovering problem
- On the ratio of optimal integral and fractional covers
- An analysis of the greedy algorithm for the submodular set covering problem
- Computational experience with approximation algorithms for the set covering problem
- 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
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Title not available (Why is that?)
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Title not available (Why is that?)
- Efficient bounds for the stable set, vertex cover and set packing problems
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- On the Fractional Solution to the Set Covering Problem
Cited In (17)
- Randomized approximation for the set multicover problem in hypergraphs
- A randomised approximation algorithm for the hitting set problem
- An approximation algorithm for the partial vertex cover problem in hypergraphs
- Online multiset submodular cover
- An effective and simple heuristic for the set covering problem
- Approximation algorithm for the multicovering problem
- Admission control with advance reservations in simple networks
- On uniform covering, adaptive random search and raspberries
- Computational experience with approximation algorithms for the set covering problem
- A Better bound of randomized algorithms for the multislope ski-rental problem
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Proximity bounds for random integer programs
- Proximity bounds for random integer programs
- Exact multi-covering problems with geometric sets
- Siting renewable power generation assets with combinatorial optimisation
- On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems
- Approximation of set multi-cover via hypergraph matching
This page was built for publication: Randomized approximation of bounded multicovering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679446)
