Algorithms for the Set Covering Problem

By A. Caprara, Paolo Toth, Matteo Fischetti. Annals of Operations Research, 2000

478 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Conditional sampling for spectrally discrete max-stable random fields (2010, background): “olves determining all hitting scenarios, which becomes computationally prohibitive for large and even moderate values of p. This issue is closely related to the NP-hard set-covering problem (see e.g. [3]). Fortunately, further detailed analysis of the probabilistic structure in the max-linear models”
Railway Track Allocation: Models and Algorithms (2012, methodology): “This sorting is inspired by the scoring technique of Caprara, Fischetti & Toth (1998) [60].”
Selected Topics in Column Generation (2002, methodology): “Dantzig and Wolfe (1960) pioneered this fundamental idea, developing a strategy to extend a linear program columnwise as needed in the solution process.”
Cooperative sensor deployment for multi‐target monitoring (2008, methodology): “Since the general ESCP is NP-complete [21], a large volume of existing work focuses on sub-optimal, polynomial-time solutions to the DSCP for various application scenarios [14, 17, 19, 20], for which a comprehensive survey can be found in [13, 16].”