Optimization of the polynomial greedy solution for the set covering problem

Journal
Proceedings of the Tenth Conference on Informatics and Information Technology. Skopje, Macedonia: Faculty of Computer Science and Engineering, Ss. Cyril and Methodius University in Skopje, Macedonia
Date Issued
2013
Author(s)
Spasovski, Stefan
Madevska Bogdanova, Ana
Abstract
This paper proposes a modification of the known and widely
used approximate greedy solution for the Set Cover Problem
- GREEDYSETCOVER algorithm. Additionally the already
known optimizations are presented and ability of their cohesion with the newly presented algorithm is confirmed. The proposed modification of the algorithm,OPTIMIZEDSETCOVER,
in the best case, gives optimal results opposite to the
GREEDYSETCOVER algorithm. In the worst case, it gives
the same results as the GREEDYSETCOVER solution without
going out of the polynomial time boundary.
File(s)
Loading...
Thumbnail Image
Name

Optimization of the Polynomial Greedy Solution for the Set Covering Problem.pdf

Size

186.99 KB

Format

Adobe PDF

Checksum

(MD5):a55c3c5179c94d4cfea7aec46c8b5610