pseudo code and runtime  for set cover brute force method

Posted on 2010-11-26
Last Modified: 2012-05-10
Can someone please share a brute-force pseudo code and runtime for the set-covering problem?
Question by:sarah2248
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
LVL 84

Expert Comment

ID: 34219986

Author Comment

ID: 34220018
that link does not provide a solution, it explains the set cover problem.
LVL 84

Expert Comment

ID: 34220030
It provides C and Pascal code to solve the problem

Author Comment

ID: 34220228
I'm actually looking for the pseudo code and runtime for a paper I'm writing I don't need the code. Thanks
LVL 37

Accepted Solution

TommySzalapski earned 500 total points
ID: 34220534
Pseudo-code for a brute force approach would be thus.
For each combination of 1 set
Check if it's a set cover
For each combination of 2 sets
Check if it's a set cover
Continue until you find a set cover.

The runtime would be the total number of combinations of sets which would be the sum of all (N choose x) where N is the number of sets and x ranges from 1 to N.

This sums to 2^N.

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
RegEx Help 18 335
LeastSquaresOptimization-ImprovingEfficiency 16 1,597
3d trilateration with multiple known points. 13 1,658
stack peek and pop methods to get binary of number 12 126
This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below.…

697 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question