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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new polynomial-time algorithm for linear programming
- 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
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- 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 (16)
- 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
- 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
Recommendations
- Title not available (Why is that?) 👍 👎
- A fast approximation algorithm for the multicovering problem 👍 👎
- Randomized approximation for the set multicover problem in hypergraphs 👍 👎
- Approximation algorithm for the multicovering problem 👍 👎
- Tight approximation bounds for maximum multi-coverage 👍 👎
- Approximability and parameterized complexity of multicover by \(c\)-intervals 👍 👎
- Approximation algorithm for the stochastic prize-collecting set multicover problem 👍 👎
- Revisiting the Approximation Bound for Stochastic Submodular Cover 👍 👎
- Tight Approximation Bounds for Maximum Multi-coverage 👍 👎
- Bicriteria Approximation of Chance-Constrained Covering Problems 👍 👎
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)
