Computational experience with approximation algorithms for the set covering problem |
| |
| Institution: | 1. School of Data and Computer Science, Sun Yat-sen University;2. State Key Laboratory of Integrated Services Networks, School of Electronic Engineering, Xidian University, Xi''an 710071, People''s Republic of China;3. School of Automation Science and Engineering, South China University of Technology;4. Guangzhou Key Laboratory of Brain Computer Interface and Applications, Guangzhou 510640, People''s Republic of China;5. School of Data and Computer Science, Sun Yat-sen University, Guangzhou, 510275, People''s Republic of China;1. Chair of Operations Research, Ruhr University Bochum, Universitätsstr. 150, Bochum D-44780, Germany;2. Lehrstuhl II für Mathematik, RWTH Aachen University, Pontdriesch 10–12, Aachen D-52056, Germany |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
