A fast approximation algorithm for the multicovering problem
The multicovering problem requires to find the (linear) least total cost for a group of sets with the assumption that given elements are covered at least given times by elements of the group. This problem is NP- complete. The paper gives an algorithm which uses O(max\(\{\) n,m\(\}\cdot n)\) time, where n is the number of prescribed sets, and m is the number of elements to be covered. The coding of the algorithm is very easy. The paper contains a sharp bound for the ratio of achieved and optimal cost, the example can be easily received from an increasing group of sets. One can ask for the probability distribution of the ratio. This is interesting because of the fact that the bound for the ratio is painfully large.
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- scientific article; zbMATH DE number 3875302 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- A finite procedure to generate feasible points for the extreme point mathematical programming problem
- Pick-and-choose heuristics for partial set covering
- The multicovering problem
- Pareto optimality and a class of set covering heuristics
- Rounding algorithms for covering problems
- A primal-dual approximation algorithm for generalized Steiner network problems
- Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
- One for the price of two: a unified approach for approximating covering problems
- Approximation algorithm for the multicovering problem
- Exact multi-covering problems with geometric sets
- A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings
- Customer order scheduling to minimize the number of late jobs
- Admission control with advance reservations in simple networks
- Minimum monopoly in regular and tree graphs
- Randomized approximation for the set multicover problem in hypergraphs
- Approximation of the clustered set covering problem
- A hybrid of max-min ant system and linear programming for the \(k\)-covering problem
- A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
- Exact algorithms for set multicover and multiset multicover problems
- LP-based covering games with low price of anarchy
- On multiple coverings of fixed size containers with non-Euclidean metric by circles of two types
- On the number and arrangement of sensors for the multiple covering of bounded plane domains
- A constant-factor approximation for multi-covering with disks
- The multi‐integer set cover and the facility terminal cover problem
- Approximation algorithms in combinatorial scientific computing
- Computing Convex Coverage Sets for Faster Multi-objective Coordination
- Heuristic solutions and confidence intervals for the multicovering problem
- Approximability of sparse integer programs
- Approximating integer programs with positive right-hand sides
- Online multiset submodular cover
- Distributed algorithms for covering, packing and maximum weighted matching
- Randomized approximation of bounded multicovering problems
- An approximation algorithm for the k-prize-collecting hitting set problem
- Hyperbolic set covering problems with competing ground-set elements
- A randomised approximation algorithm for the hitting set problem
- Set multi-covering via inclusion-exclusion
- Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
- A finite cutting plane method for solving linear programs with an additional reverse convex constraint
- Dynamic programming based algorithms for set multicover and multiset multicover problems
This page was built for publication: A fast approximation algorithm for the multicovering problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082267)
