Randomized approximation of bounded multicovering problems
From MaRDI portal
Publication:679446
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
- scientific article; zbMATH DE number 3869066 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A fast approximation algorithm for the multicovering problem
- A new polynomial-time algorithm for linear programming
- An analysis of the greedy algorithm for the submodular set covering problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for combinatorial problems
- Computational experience with approximation algorithms for the set covering problem
- Efficient bounds for the stable set, vertex cover and set packing problems
- How to Allocate Network Centers
- On the Fractional Solution to the Set Covering Problem
- On the ratio of optimal integral and fractional covers
- Optimization, approximation, and complexity classes
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Vertex packings: Structural properties and algorithms
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
Cited in
(19)- Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis
- On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems
- Proximity bounds for random integer programs
- Proximity bounds for random integer programs
- Admission control with advance reservations in simple networks
- An effective and simple heuristic for the set covering problem
- Online multiset submodular cover
- Approximation algorithm for the multicovering problem
- Approximation of set multi-cover via hypergraph matching
- A randomised approximation algorithm for the hitting set problem
- Approximate set union via approximate randomization
- Siting renewable power generation assets with combinatorial optimisation
- Exact multi-covering problems with geometric sets
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- On uniform covering, adaptive random search and raspberries
- Randomized approximation for the set multicover problem in hypergraphs
- Computational experience with approximation algorithms for the set covering problem
- An approximation algorithm for the partial vertex cover problem in hypergraphs
- A Better bound of randomized algorithms for the multislope ski-rental problem
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)
