The multicovering problem

DOI10.1016/0377-2217(92)90122-PzbMath0759.90072OpenAlexW1995634446MaRDI QIDQ1205691

Nicholas G. Hall, Dorit S. Hochbaum

Publication date: 1 April 1993

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(92)90122-p

zbMATH Keywords

heuristicscutting planesset coveringmulticovering

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A hybrid Lagrangean heuristic with GRASP and path-relinking for set \(k\)-covering, Experiments with LAGRASP heuristic for set \(k\)-covering, Exact multi-covering problems with geometric sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast approximation algorithm for the multicovering problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Algorithms for large scale set covering problems
• An algorithm for set covering problem
• Cluster Analysis: An Application of Lagrangian Relaxation
• Cutting planes from conditional bounds: A new approach to set covering
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A Greedy Heuristic for the Set-Covering Problem
• Database Location in Computer Networks
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• The Set-Covering Problem: A New Implicit Enumeration Algorithm
• Validation of subgradient optimization
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems
• The traveling-salesman problem and minimum spanning trees: Part II
• Depth-First Search and Linear Graph Algorithms