View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Greedy algorithm for Set Cover problem

Join the 15-year community celebration.

Play games and win prizes!

» Learn more

2.5 | 2 ratings Rate this file 29 Downloads (last 30 days) File Size: 4.22 KB File ID: #29650 Version: 1.1

Greedy algorithm for Set Cover problem



08 Dec 2010 (Updated )

The well known greedy algorithm for solving Set Cover problem, with a few changes

| Watch this File

File Information

This function contains the well known greedy algorithm for solving Set Cover problem (Chvátal, 1979), with two small modifications:
* In case of more than one possible choice at a certain step, the biggest set is chosen;
* Once the solution is found, we check the selected sets to find a better cover solution, removing a set if is a subset of the union of the other set.

If you use this code, please cite the article for which it was implemented:
F. Gori, G. Folino, M.S.M. Jetten, E. Marchiori
"MTR: Taxonomic annotation of short metagenomic reads using clustering at multiple taxonomic ranks", Bioinformatics 2010.
doi = 10.1093/bioinformatics/btq649


Additional information:

GREEDYSCP Greedy SCP algorithm.
   [SolC,SolL] = GREEDYSCP(C, L) if C is an array, creates a cell array SolC that is a solution of Set Cover Problem defined by C, where C{i} = S_i, an input set made by some of the elements we want to cover; SolC is made by the cells of C selected by the algorithm. The elements that we want to cover are indicates by numbers from 1 to n, where n is the number of elements we want to cover; therefore, C{i} is a vector of integers between 1 and n.

   If C is a logical or numerical array of n rows, where C(j,i) > 0 iff element j is contained in set S_i, the output SolC will be a logical array made by the column of log(C) corresponding to the solution

   If a vector L of integer labels of the elements of C is provided, SolL contains the labels corresponding to SolC. Otherwise SolL contains the positions of elements of SolC in C. SolC and SolL elements are sorted in ascending order of SolL.

MATLAB release MATLAB 7.10 (R2010a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (4)
15 Sep 2015 Lince Varghese  
09 Jun 2015 Reem Allam

How should be input setslabel ?

Comment only
22 Apr 2015 prety krishnamoorthy

setcells error occurs

Comment only
09 Dec 2010 Joan

Joan (view profile)

09 Dec 2010 1.1

* Output has the same class of input; input can be an array or a cell-array;
* Array and cell are processed with target implementations of the same algorithm

Contact us