Efficiency comparison of exact and approximate algorithms for solving set covering problem
https://doi.org/10.23947/1992-5980-2017-17-3-137-144
Abstract
About the Authors
Igor S. KonovalovRussian Federation
Sergey S. Ostapenko
Russian Federation
Valery G. Kobak
Russian Federation
References
1. Konovalov, I.S., Fatkhi, V.A., Kobak, V.G. Sravnitel'nyy analiz raboty zhadnogo algoritma Khvatala i modifitsirovannoy modeli Goldberga pri reshenii vzveshennoy zadachi nakhozhdeniya minimal'nogo pokrytiya mnozhestv. [Comparative analysis of work of Chvatal greedy algorithm and modified Goldberg model under solving the problem on determining minimal set covering.] Trudy SKF MTUSI. Rostov-on-Don: PTs «Universitet» SKF MTUSI, 2015, pp. 366–371 (in Russian).
2. Konovalov, I.S., Fatkhi, V.A., Kobak, V.G. Strategiya elitizma modifitsirovannoy modeli Goldberga geneticheskogo algoritma pri reshenii zadachi pokrytiya mnozhestv. [Elitism strategy of modified Goldberg model of genetic algorithm in solving the set covering problem.] Herald of Computer and Information Technologies, 2016, no. 4, pp. 50–56 (in Russian).
3. Konovalov, I.S., Fatkhi, V.A., Kobak, V.G. Primenenie geneticheskogo algoritma dlya resheniya zadachi pokrytiya mnozhestv. [Application of genetic algorithm for the set-covering problem solution.] Vestnik of DSTU, 2016, no. 3pp. 125–132 (in Russian).
4. Eremeev, A.V. Geneticheskiy algoritm dlya zadachi o pokrytii. [A genetic algorithm for the covering problem.] Discrete Analysis and Operations Research, 2000, ser. 2, vol. 7, no. 1, pp. 47–60 (in Russian).
5. Eremeev, A.V., Zaozerskaya, L.A., Kolokolov, A.A. Zadacha o pokrytii mnozhestva: slozhnost', algoritmy, eksperimental'nye issledovaniya. [The set covering problem: complexity, algorithms, and experimental investigations.] Discrete Analysis and Operations Research, 2000, ser.2, vol. 7, no. 2, pp. 22–47 (in Russian).
6. Holland, J.H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975, p. 245.
7. Goldberg, D.E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989, p. 432.
8. Batishchev, D.I. Geneticheskie algoritmy resheniya ekstremal'nykh zadach. [Genetic algorithms for solving extremal problems.] Voronezh: izd-vo Voronezh. gos. tekhn. un-ta, 1995, 121 p. (in Russian).
9. Gladkov, L.A., Kureychik, V.V., Kureychik, V.M. Geneticheskie algoritmy. [Gtnetic algorithms.] Moscow: FIZMATLIT, 2010, 368 p. (in Russian).
10. Alekseev, O.G., Grigoryev, V.F. Nekotorye algoritmy resheniya zadachi o pokrytii i ikh eksperimental'noe issledovanie na EVM. [Some algorithms for solving the covering problem and their experimental computed study.] Computational Mathematics and Mathematical Physics, 1984, vol. 24, no. 10, pp. 1565–1570 (in Russian).
Review
For citations:
Konovalov I.S., Ostapenko S.S., Kobak V.G. Efficiency comparison of exact and approximate algorithms for solving set covering problem. Vestnik of Don State Technical University. 2017;17(3):137-144. (In Russ.) https://doi.org/10.23947/1992-5980-2017-17-3-137-144