In combinatorics, it is the problem of selecting a minimum number of sets so that these sets combined contain all the elements found in some reference set.
Questions tagged [set-cover]
44 questions
7
votes
1 answer
Is this a minimal set-cover problem?
I have the following scenario (preliminary apologies for length, but I wanted to be as descriptive as possible):
I am presented with a list of "recipes" (Ri) that must be fulfilled, in the order presented, to complete a given task. Each recipe…
laramieman
- 73
- 3
6
votes
4 answers
Variation on set cover problem in R / C++
Given a universe of elements U = {1, 2, 3,...,n} and a number of sets in this universe {S1, S2,...,Sm}, what is the smallest set we can create that will cover at least one element in each of the m sets?
For example, given the following elements…
jedfrancis
- 251
- 1
- 6
6
votes
2 answers
Query for Set Cover
Good Day, I would like to implement a T-SQL query for the Set Cover Problem but have been unable to find any hints on how to do this in SQL.
In my case, my table just has two columns (IDnumber and Mut) and I want to find the minimum number of…
user918967
- 2,049
- 4
- 28
- 43
5
votes
3 answers
minimal multiplications vs a set-cover issue
I have a set I ={P1, P2, ..., Pm} , and n finite subsets of I, denoted by R1,R2,...,Rn as follows:
R1 = {P1, P2}
R2 = {P2, P4}
R3 = {P2, P3, P4}
R4 = {P1, P2, P4}
....
where Pi denotes an integer.
For each Ri, I want to compute the product of all…
John Smith
- 617
- 3
- 16
4
votes
1 answer
Set cover approximation in R
I'm trying to solve or implement an approximation to the set cover problem in R. Given a data frame like this.
sets n
1 s1 1
2 s1 2
3 s1 3
4 s2 2
5 s2 4
6 s3 3
7 s3 4
8 s4 4
9 s4 5
The unique number of elements in column n…
mpalanco
- 12,960
- 2
- 59
- 67
4
votes
2 answers
Brute force complexity of Set Cover
We can solve Set Cover Problem by forming all the possible sets combination and verifying whether it is the minimum solution. Now we can have at most 2^n such sets combination where 'n' is the number of Set.
So, the complexity of this approach…
Naved Alam
- 827
- 9
- 25
4
votes
1 answer
Minimum set cover
I would like to solve a minimum set cover problem of the following sort. All the lists contain only 1s and 0s.
I say that a list A covers a list B if you can make B from A by inserting exactly x symbols.
Consider all 2^n lists of 1s and 0s of…
Simd
- 19,447
- 42
- 136
- 271
3
votes
1 answer
Complexity measurement of NP-complete
For example, the set-cover decision problem is known to be a NP-complete problem. The input of this problems is a universe U, a family S of subsets of U, and an integer k ().
One thing that I'm confused with is that if we let k=1, then obviously…
kostio
- 33
- 4
3
votes
1 answer
Greedy Set Coverage algorithm built by *removing* sets
I am trying to implement a solution for a set coverage problem using a greedy algorithm.
The classic greedy approximation algorithm for it is
input: collection C of sets over universe U , costs: C→R ≥0
output: set cover S
1. Let S←∅.
2.…
Dale M
- 2,453
- 1
- 13
- 21
2
votes
0 answers
Confused about the for loop in the Set Covering Problem (Greedy Algorithms)
This is my first time learning data structure and algorithms. I am stuck in the Grokking Algorithm Chapter 8 Greedy Algorithms, where there is a simple Set Covering Problem given to the readers.
Is there a simpler example of source code which I can…
daiman00
- 25
- 2
2
votes
0 answers
Minimal vs Minimum solution for Set Cover
There is a set of items that need to be covered. The subsets of these items are available. If we ask for the minimum number of these subsets that cover the whole items, the problem is the well-known Set Cover problem. Let denote the solution to the…
Arash Vaezi
- 21
- 1
2
votes
1 answer
Set cover: Generating test instances
I'm looking forward to solve the Set Cover Problem using a genetic algorithm. I've been looking everywhere for some good test instances, but without any big success.
What I'm looking for would be some instances under the form: a set U = {1,2,...,n}…
serban0
- 23
- 3
2
votes
1 answer
How to optimize this suboptimal Set-Cover solution?
I wrote this program to test how long it would take to "solve" the set-cover problem.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using MoreLinq;
namespace SetCover
{
class…
mpen
- 272,448
- 266
- 850
- 1,236
2
votes
2 answers
How to find smallest number of lists needed to cover all elements in another list
I'm working on a code using Matlab in which I need to find the least number lists (in some set of given lists) necessary to cover all the elements of a reference list.
For example, say my reference list is
X = [0 1 2 3 4 5 6 7 8 9]
And I have a…
matlab137
- 21
- 2
2
votes
1 answer
Is there any appproximate algorithms in set cover when there are too many sets, say, 2^n sets?
I am recently working on a problem which I think is a fork of the set cover problem. However, the number of sets in my problem is as large as 2^n. And the approximate alogrithms I've found seem to be only effective when there are not too many sets.…
Yihong Xiang
- 75
- 5