# Questions tagged [set-cover]

Set cover is a well-known NP-complete problem: given a collection of sets, find as small as possible a subcollection whose union is the same as the union of the entire collection.

103 questions
Filter by
Sorted by
Tagged with
25 views

### Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm

I am trying to solve the Budgeted Maximum Coverage Problem. I have read and implemented the greedy and modified-greedy methods to solve it, as proposed by Khuller. Both are approximation algorithms. ...
123 views

### set cover to edge cover

I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I ...
22 views

### Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
92 views

62 views

### Triangles covering all vertices of a tri-partite graph

This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers. I'm designing fictional fruits. Each fruit has three attributes; color, taste ...
80 views

156 views

### maximum coverage version of dominating set

The dominating set problem is : Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ ...
41 views

44 views

### Weighted Set Cover Problem Minimizing Average Weight

In the traditional weighted set cover problem, we aim at minimizing the sum of the weight of the selected sets. Is there any problem/literature that aim at minimizing the average weight of the ...
144 views

### Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria

Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$, find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in ...
67 views

### Clarification on NP-hardness and hardness of approximation results for set cover?

I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements. I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it ...
181 views

### Approximation algorithm for weighted set cover, using multiplicative weights

It is known that the problem of fractional set cover can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ...
127 views

### Solving the Size-Constrained Weighted Set Cover Problem

I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the ...
100 views

### Minimal edge cover of the hypergraph

We know that minimal edge cover for the normal graph is polynomial time solvable. Is it also true for hypergraph?
591 views

### set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
2k views

### Given a set of intervals on the real line, find a minimum set of points that “cover” all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
1k views

Suppose $G$ is a connected graph and $S$ is a vertex cover. Prove that $S$ is also a dominating set. Can I get some help with proving this? I know that a dominating set in an undirected graph $G=(V,E)... 0answers 78 views ### Specialized Algorithm for Set-Cover with$k=3$I know that the Set-cover problem with$n$elements and a universe of size$N$is NP complete. Also, the problem is has parameterized complexity regarding the number of sets$k$that should cover the ... 1answer 49 views ### Probability of randomly designated subsets cover the universe Let$U=\{1,2,\ldots,n\}$and$S \subseteq \mathscr{P}(U)$. Let$T$be a subset of$S$, randomly constructed selecting independently each element of$S$with probability$p$. Is there a polynomial ... 1answer 43 views ### About a pre-processing step for primal-dual weighted set cover problem I was reading the paper titled "Primal-dual RNC approximation algorithms" by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1. They present a dual fitting based algorithm ... 1answer 54 views ### How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem? Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set$S$of size$k$, if there ... 1answer 450 views ### Hardness of approximating Minimum Cardinality Exact Cover The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint. Formally, given a collection of subsets$S$of a finite set$U$, the problem asks for ... 1answer 26 views ### Ensure groups of four 3-tuples have 9 unique numbers Note: I know the numbers are arbitrary, but this problem about this size has practical implications. It is an applied algorithm problem. Suppose you have 200 bins. Each bin would be very happy to ... 0answers 154 views ### Applications of Set Covering I am interested in the applications for set covering. On Wikipedia and this thread, I read that it is used in antivirus programs, random testing in software, and personnel scheduling. Does anyone know ... 0answers 100 views ### How to enumerate all partitioning of a set to k-subsets of size at most b I'm looking for an algorithm to generate/enumerate all possibilities for partitioning a set of size$n$to$k$non-empty subsets, each with size at most$b$. More specifically, given a set$V$where$...
There are $n$ points in a plane. The decision problem is to identify whether there exists a set $S$ of $k$ or less points from the $n$ points such that all $n$ points are at most $d$ distance from ...