Questions tagged [set-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
63 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 ...
1
vote
0answers
46 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 ...
2
votes
1answer
50 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}$ ...
1
vote
1answer
109 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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
55 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 ...
0
votes
0answers
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 ...
3
votes
1answer
42 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 ...
1
vote
0answers
37 views

An LP with two covering constraints - how to round

I came across an LP with two covering problems, and I wonder how to find a good approximation. For the relevant part of the LP: We have a set $E$ , for each $e\in E$ we have a corresponding set $Y_{e}\...
3
votes
0answers
39 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 ...
2
votes
1answer
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 ...
0
votes
0answers
35 views

Weighted-Set Cover Approximation

So in the weighted-set cover problem, I need to determine the minimum weight cover. My algorithm calculates the efficiency for each set: ...
3
votes
1answer
57 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 ...
2
votes
1answer
104 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 ...
1
vote
0answers
77 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 ...
0
votes
1answer
53 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?
1
vote
2answers
373 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 ...
3
votes
1answer
530 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 ...
1
vote
1answer
311 views

Every vertex cover is a dominating set

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)...
5
votes
0answers
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 ...
4
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
6
votes
1answer
226 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 ...
2
votes
1answer
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 ...
1
vote
0answers
122 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 ...
1
vote
0answers
91 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 $...
2
votes
1answer
117 views

An exact solution for biclique vertex-cover problem on a bipartite graph

The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs). It has been shown that "Biclique Vertex-...
1
vote
1answer
60 views

NP completeness proof of sensor selection problem

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 ...
1
vote
1answer
348 views

Reverse cartesian product matching all given rows

I´m looking for an efficient algorithm that will find reverse cartesian products. Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A_{i,1} \times A_{i,2} \times \...
1
vote
1answer
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 ...
5
votes
3answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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\...
1
vote
1answer
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 ...
1
vote
2answers
759 views

How to enumerate minimal covers of a set

I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$. What is the best algorithm for ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
15
votes
1answer
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 ...
1
vote
1answer
441 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? ...
3
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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, ...
1
vote
0answers
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?
0
votes
1answer
264 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 ...
0
votes
0answers
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$. ...
4
votes
1answer
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 ...
1
vote
2answers
2k views

Vertex cover algorithms for directed graphs?

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 ...