Google Scholar

Wednesday, March 08, 2006

A very simple non optimized C++ implementation of approximation algorithms for Minimum Weighted Set Cover problem
MWSCP.h
MWSCP.cpp
MWSCP.solveGreedy() implements Greedy algorithm
MWSCP.solveLayered() implements Layered algorithm

As it is well-known solveLayered is optimal in respect to the MWSCP instances with bounded frequency of elements. If the frequence of element is bounded by k, then solveLayered algorithm produce approximate solution greater not more k times then optimal solution.
Greedy algorithm may produce log n factor solution even for bounded frequency instance of the MWSC problem.

I have tried these algorithm for many randomly generated instances of the MWSCP.
solveGreedy outperforms solveLayered around 10 times, while produce a solution a few times cheaper