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.

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
80 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
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 ...
3
votes
0answers
172 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
54 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
46 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 ...
2
votes
0answers
51 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?
1
vote
0answers
20 views

Complexity of solving fractional constrained set multicover

Recently, I've encountered the following problem: Given a collection of sets $S_1 \dots S_n$ of elements $e_1 \dots e_k$ with element $e_k$ denoted privileged, and a $k-1$-vector $r$, choose at most $...
1
vote
1answer
809 views

Is time complexity of the greedy set cover algorithm cubic?

I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements....
1
vote
0answers
99 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
45 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
128 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
156 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
101 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
41 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
34 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\...
0
votes
0answers
47 views

Minimum Dominating Set

Consider a graph $G$ with minimum degree $d$, we know through sets cover, it's possible to find the one dominating set $S$ that covers $G$ such that $$S\leq O(\log n)\frac{n}{d} $$ with high ...
0
votes
0answers
35 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
23 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
1answer
129 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
82 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$. ...