A fast approximation algorithm for the multicovering problem
From MaRDI portal
Publication:1082267
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
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial optimization (90C27) Boolean programming (90C09)
Related Items
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
