Computational experience with approximation algorithms for the set covering problem

✍ Scribed by Tal Grossman; Avishai Wool

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 722 KB
• Volume: 101
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(96)00161-0

✦ Synopsis

The Set Covering problem (SCP) is a well known combinatorial optimization problem, which is NP-hard. We conducted a comparative study of nine different approximation algorithms for the SCP, including several greedy variants, fractional relaxations, randomized algorithms and a neural network algorithm. The algorithms were tested on a set of random-generated problems with up to 500 rows and 5000 columns, and on two sets of problems originating in combinatorial questions with up to 28160 rows and 11264 columns•

On the random problems and on one set of combinatorial problems, the best algorithm among those we tested was a randomized greedy algorithm, with the neural network algorithm very close in second place. On the other set of combinatorial problems, the best algorithm was a deterministic greedy variant, and the randomized algorithms (both randomized greedy and neural network) performed quite poorly. The other algorithms we tested were always inferior to the ones mentioned above. (~ 1997 Elsevier Science B.V.