Questions tagged [set-cover]

The tag has no usage guidance.

19 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
56 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 ...
3
votes
0answers
40 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 ...
3
votes
0answers
146 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
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 ...
2
votes
0answers
41 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
0answers
61 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 ...
1
vote
0answers
42 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}\...
1
vote
0answers
85 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 ...
1
vote
0answers
132 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
93 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 $...
1
vote
0answers
32 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
32 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
0answers
44 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
0answers
18 views

Set cover problem satisfying half constraints

Consider a variation of the set cover problem in which we only have to cover some certain amount of elements. Is this problem still NP-hard? I guess yes? Is there a good reference?
0
votes
0answers
33 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 ...
0
votes
0answers
13 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 ...
0
votes
0answers
39 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: ...
0
votes
1answer
67 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 ...
0
votes
0answers
76 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$. ...