# Questions tagged [set-cover]

The tag has no usage guidance.

84 questions
Filter by
Sorted by
Tagged with
43 views

### Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem

The unweighted maximum coverage problem is defined as follows: Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$. Objective: find a subset $S' \subseteq S$ such ...
41 views

### Hitting Set Problem with non-minimal Greedy Algorithm

The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
106 views

### Is Finding A Hitting Set of Size n/2 NP-Hard?

In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E. In decision version of the problem, we are asked ...
32 views

### Point of Interest Problem

You are in a xy plane with a set of points F. You also have a collection P of N sets { P1,...., Pn} where each of the set consist of points of the form (Px,Py). Each set has a different number of ...
54 views

### Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”

In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality. In Fig. 1.3, the author says a black colored leaf ...
12 views

### Set Cover with multiple covers

In the Set Cover problem we need to cover each element at least once. I'm considering the case where I want each element to be covered at least $k$ times with constant $k$. I consider the classic LP ...
14 views

### Hardness of approximation statement clarification?

In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved ...
41 views

### Is this variation of set-cover NP-hard to approximate?

The classic set-cover problem is described as follows: Let $S = \{s_1, ..., s_n\}$ be a target set, and let $\Lambda = \{A_1, ..., A_m: A_i \subset S\}$ be a collection of subsets of $S$. The ...
37 views

54 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 ...
43 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 ...
38 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 ...
43 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 ...
222 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 ...
24 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 ...
121 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 ...
91 views

278 views

### Maximum weighted disjoint set union

I would like to know whether the following problem is a standard problem that has been considered in the research literature. I performed some searches, which have not produced results. I call this ...
123 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 ...
31 views

### Algorithms for MinSat when all literals are positive?

I am given a set $U = \{1, \cdots, n\}$ and a set of subsets $C_1, \cdots, C_k$ of $U$; here the sets are all the same size. The minimum set-cover problem of course is to find the minimum number of ...
31 views

### NP-hardness of maximum set cover with element-level submodular function

Consider the following generalization of maximum set cover problem: Given a collection $C$ of subsets of a finite set $S$. Find $C^{'} \subseteq C$ of cardinality $k$ that maximizes \[ \sum\...
188 views

### Verifying if a greedy solution is optimal for a specific instance (Set cover)

Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution. Is there an efficient way of verifying if, for that particular instance, the given solution ...
86 views

### Optimal covering of 2D matrix elements given spatial constraints

I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction. I've ...
51 views

### Given multiple families of sets, select a set from each such that the intersection of selected sets is a correspondence

Let $X = \{x_1, ... , x_k\}$ and $Y = \{y_1, ... , y_h\}$. A subset $S \subset X \times Y$ is a correspondence if : $\forall x, \exists y, (x,y) \in S$ and $\forall y, \exists x, (x,y) \in S$ That ...
490 views

### Grid covering by rectangles

We have a $N_1 \times N_2$ grid. We have a collection of rectangles on this grid, each rectangle can be represented as a $N_1$-by-$N_2$ binary matrix $R$. We want to cover the grid with those ...
440 views

### Set cover problem with sets of size 2

I have a question about the Set Cover problem: If I get a universe $U$, and $m$ subsets of size exactly $2$, and an integer $k$. Is this problem is still NP-C or I can solve it on a polynomial time? ...
136 views

### 2-approximation edge-cover algorithm using primal-dual method

The problem Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle. So far I managed to represent the ...
38 views

### On the complexity of Unique Coverage Problem restricted to geometrical settings

I come to you with a problem I have been struggling with for the past few weeks. I would like to classify (complexity) a special case of Unique Coverage. To set the mood on, I will start by ...
69 views

### Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets

I am trying to generate a list of digit triplets to specify stimuli in an auditory (speech-in-noise) perception experiment. Each triplet has to have three different digits (i.e., no repetition within ...
71 views

### Approximation rate for Greedy Set Cover algorithm (RESOLVED)

Set Cover: Consider a set of points X and Si a subset of X. The goal is to get the minimum number of subsets Si such as all points in X are covered. An example is shown by figure bellow. In this case, ...
42 views

### Smallest set non-disjoint with other given sets

Given a number of sets, what is the best algorithm to calculate the smallest set S such that S is not disjoint with any of the given sets?
263 views

### Reduce Clique to Set Cover

Is it possible directly to reduce clique to set cover? I know that there are some ways of direct reduction from Clique to Vertex Cover and from Vertex Cover to Set Cover, so I am very interested to ...
2k views

### What are the real world applications of set cover problem?

I am studying about set cover problem and wondering that which problems in real world can be solved by set cover. I found that IBM used this problem for their anti-virus problem, so there should be ...
75 views

### Variation on weighted set cover, cover by consecutive pairs

Input: A set $N = \{1, \dots, n\}$, subsets/consecutive pairs $S_1 = \{1,2\}, \dots, S_n = \{n,1\}$ with associated costs $c_1, \dots, c_n \in \mathbb{N} \cup \{0\}$, and a subset $B \subseteq N$. ...
165 views

### Is 'double max-$k$ vertex-cover' NP-hard?

Consider the following problem, which I have called '$\mathsf{\text{double max$k$-vertex-cover}}$': Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices ...
I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph. Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a ...
We have a group of $n$ people. We are given a list of who must buy presents for whom within the group. Each person might need to buy/receive any number of presents, or possibly none at all. In a ...