# Greedy algorithm for Set Cover problem (Scripts) 1.0

Average Rating
User Rating:
Visitors Rating:
My rating:

• Last update: 6 years ago
• Price: Free |
• Operating system: Linux, Mac OS X, Win All, BSD, Solaris
• Publisher: Fabio Gori
See full specifications

## Greedy algorithm for Set Cover problem (Scripts) Publisher's description

### This function contains the well known greedy algorithm for solving Set Cover problem (ChvГЎtal, 1979)

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

---

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.

#### System Requirements:

MATLAB 7.10 (2010a)
Program Release Status: Major Update
Program Install Support: Install and Uninstall

#### Greedy algorithm for Set Cover problem (Scripts) Tags:

Click on a tag to find related softwares

## Most Popular

ASK, OOK, FSK, BPSK, QPSK, 8PSK modulation 1.1
ASK, OOK, FSK, BPSK, QPSK, 8PSK modulation contain several functions for digital modulation simulation
Simulink Communication Labs 1.1
Simulink Communication Labs allows you to learn communication systems in greater depth.
M-QAM modulation and demodulation 1.1
M-QAM modulation and demodulation is the QAM modulation and demodulation tech.
LZW Compression/Decompression 1.1
LZW Compression/Decompression - Updated LZW compressor and decompressor with reasonable performance
InSPIRE utility to plot a 2D displacement field (Scripts) 1.0
This program plots the deformation field (displace vectors) contained in vector.txt.