An exact algorithm for the maximal covering problem

DOI10.1002/(SICI)1520-6750(199604)43:3%3C435::AID-NAV8%3E3.0.CO;2-AMaRDI QIDQ4883162zbMATH OpenOpenAlexFDO

Authors Brian T. Downs, Jeffrey D. Camm

Publication date 1 July 1996

Full work available at URL https://doi.org/10.1002/(sici)1520-6750(199604)43:3%3C435::aid-nav8%3E3.0.co;2-a

zbMATH Keywords

branch-and-boundLagrangian relaxationgreedy heuristicsmaximal covering problembounding schemesdual-based solution methodsrobust, exact algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Discrete location and assignment (90B80)

Recommendations

• An approximation algorithm for the total covering problem
• An exact algorithm for a class of geometric set-cover problems
• Efficient algorithms for the max \(k\)-vertex cover problem
• Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
• Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
• scientific article; zbMATH DE number 5371016
• A branch-and-cut algorithm for the maximum covering cycle problem
• On approximation of max-vertex-cover
• Exact algorithms for set multicover and multiset multicover problems
• An exact algorithm for the maximum clique problem

Cited in

(29)

• A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem
• Bayesian coverage optimization models
• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• Emergency service systems: The use of the hypercube queueing model in the solution of probabilistic location problems
• Accelerated Benders decomposition and local branching for dynamic maximum covering location problems
• scientific article; zbMATH DE number 1226311 (Why is no real title available?)
• Fuzzy logic based algorithms for maximum covering location problems
• scientific article; zbMATH DE number 2000148 (Why is no real title available?)
• Mixed-integer programming approaches for the time-constrained maximal covering routing problem
• A practical heuristic for maximum coverage in large-scale continuous location problem
• Efficient presolving methods for solving maximal covering and partial set covering location problems
• A VNS-LP algorithm for the robust dynamic maximal covering location problem
• On the overlap area of a disk and a piecewise circular domain
• A hybrid adaptive iterated local search heuristic for the maximal covering location problem
• Intelligent-guided adaptive search for the maximum covering location problem
• A mean-shift algorithm for large-scale planar maximal covering location problems
• A hybrid method for the probabilistic maximal covering location-allocation problem
• A constructive proof of swap local search worst-case instances for the maximum coverage problem
• A branch-and-cut algorithm for the maximum covering cycle problem
• The Maximal Conditional Covering Problem
• Solving the maximal covering location problem with heuristic concentration
• Iterated greedy algorithms for the maximal covering location problem
• A mixed integer linear program and tabu search approach for the complementary edge covering problem
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• A procedure for solution of the problem of optimal covering of a finite set
• scientific article; zbMATH DE number 8033 (Why is no real title available?)
• The Exact Subset MultiCover problem
• An optimal algorithm for the minimum disc cover problem
• Benders decomposition for very large scale partial set covering and maximal covering location problems

This page was built for publication: An exact algorithm for the maximal covering problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4883162)