A fast approximation algorithm for the multicovering problem

DOI10.1016/0166-218X(86)90016-8zbMath0602.90110OpenAlexW2069870307MaRDI QIDQ1082267

Nicholas G. Hall, Dorit S. Hochbaum

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90016-8

zbMATH Keywords

approximation algorithmheuristicmulticovering problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (29)

Customer order scheduling to minimize the number of late jobs ⋮ A primal-dual approximation algorithm for generalized Steiner network problems ⋮ A finite procedure to generate feasible points for the extreme point mathematical programming problem ⋮ A hybrid of max-min ant system and linear programming for the \(k\)-covering problem ⋮ Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms ⋮ Pick-and-choose heuristics for partial set covering ⋮ Rounding algorithms for covering problems ⋮ A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings ⋮ Approximability of sparse integer programs ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ A finite cutting plane method for solving linear programs with an additional reverse convex constraint ⋮ Approximating integer programs with positive right-hand sides ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ LP-based covering games with low price of anarchy ⋮ Admission control with advance reservations in simple networks ⋮ Randomized approximation of bounded multicovering problems ⋮ The multicovering problem ⋮ Dynamic programming based algorithms for set multicover and multiset multicover problems ⋮ Minimum monopoly in regular and tree graphs ⋮ Hyperbolic set covering problems with competing ground-set elements ⋮ The multi‐integer set cover and the facility terminal cover problem ⋮ Approximation algorithm for the multicovering problem ⋮ On Multiple Coverings of Fixed Size Containers with Non-Euclidean Metric by Circles of Two Types ⋮ A randomised approximation algorithm for the hitting set problem ⋮ On the Number and Arrangement of Sensors for the Multiple Covering of Bounded Plane Domains ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Exact multi-covering problems with geometric sets ⋮ Pareto optimality and a class of set covering heuristics ⋮ Randomized approximation for the set multicover problem in hypergraphs

Cites Work

• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Unnamed Item
• Unnamed Item

This page was built for publication: A fast approximation algorithm for the multicovering problem