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.
129
questions
0
votes
1
answer
21
views
Enumerating proper intersections
Let
$U \subset \mathbb{N}$ be a finite universe set;
$B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then $b \...
0
votes
0
answers
41
views
Reduction from novel problem to Set Cover
i would like to perform a reduction for my novel problem to preferably the set cover problem, but i am a bit lost..
My problem can be described as follows:
Suppose you have given an binary word as ...
1
vote
1
answer
37
views
Maximum Weighted coverage approximation algorithm?
I am looking for an algorithm similar to the unweighted maximum coverage. However, I have been unable to find a similar algorithm for the weighted version.
How should I modify the algorithm above to ...
- 141
2
votes
0
answers
82
views
Data structure for prefix covering
I have a list $[1, 2, \ldots, T]$. I want to create a collection of subsets, such that:
each element belongs to a small number of subsets
each prefix is a union of small number of subsets (these ...
- 21
0
votes
0
answers
24
views
How to prove Set-Cover problem is NP hard via reduction from Clique problem?
Since I know that the reduction Clique $\leq_{p}$ Vertex-Cover and Vertex-Cover $\leq_{p}$ Set-Cover are possible, I know how to show this using transitivity property of reductions. However is there ...
2
votes
1
answer
61
views
Minimal set of elements needed to satisfy property counts
I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain ...
2
votes
1
answer
74
views
Algorithm to find intersection between collection of sets
I have two dataframes representing products two distributors sell. They look like this:
df1 for distributor 1.
...
- 280
0
votes
1
answer
46
views
Minimal Hitting Sets Problem
Let $\mathcal{I} = \{I_0, \ldots, I_{m-1}\}$ a collection of subset of some universe $U$.
We want to find a partition $P$ of $\mathcal{I}$ of minimal cardinality such that the intersection of each set ...
- 133
3
votes
0
answers
142
views
Maximum set cover with non-overlap
Let the universe be the set $U$ and a set of subsets $S$ be such that $\cup_{s \in S} s = U$. I am interested in computing the longest sequence of sets $s_1, ..., s_k$ such that:
$s_i \in S$ $\forall ...
- 31
0
votes
1
answer
95
views
Greedy Algorithm for Geometric Set Cover
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem.
The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
- 63
0
votes
1
answer
59
views
Geometric Set Cover in one dimension
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem.
The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
- 63
0
votes
0
answers
23
views
maximum k- coverage when the universe is streaming
I am studying the maximum k-coverage problem when the universe is streaming (rather than the subsets). Formally, Let $U$ be a universe set which is unknown at the beginning. We have $n$ subsets ...
- 115
1
vote
1
answer
40
views
Modified set cover to identify "orthogonal" partitions
Setup
I have a non-empty set of elements $U$ that are arranged spatially.
I would like to partition $U$ into $N$ non-empty, disjoint subsets, $A_i$, having up to $M$ elements each. Each subset is only ...
- 11
1
vote
1
answer
25
views
Efficiently covering a finite set of points in $\mathbb{Z}^3$ by fixed size, axis-aligned cubes?
In my problem of interest I have an arbitrary, finite set $S \subset \mathbb{Z}^3$. And I would like to cover $S$ with a set $C \subset \{T | T \subset \mathbb{Z}^3 \textrm{ is an axis-aligned cube of ...
- 33
2
votes
1
answer
159
views
Lower Bounding Set Cover's Approximation Ratio
I am reading Slavik's paper A Tight Analysis of Greedy Set Cover. Specifically, Slavik considers the unweighted version of set cover where the ground set is ${U = \{1,\ldots,m\}}$ for arbitrarily ...
- 121
2
votes
0
answers
44
views
Lowest total cardinality mutually exclusive construction of a superset
Let there be $N$ sequences containing at least one set each. Each set has at least one element each.
Select exactly one set from each sequence. The selection within each sequence is mutually exclusive....
- 237
2
votes
0
answers
135
views
Exact Cover variant: partition a family of subsets into exact coverings
I have found that a problem that I'm analyzing is equivalent to the following variant of the Exact Cover problem:
Partition into $k$ Exact Covers
Input: A universe ...
- 111
1
vote
1
answer
168
views
Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?
I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2.
Set cover problem with sets of size 2
The ...
1
vote
1
answer
145
views
Trivial vertex cover in regular graph is 2-approximation Proof
I need to show that in any regular graph, taking all nodes gives a 2-approximation vertex cover.
My attempt: I am proving that every $k$-regular graph can be reduced to a 2-regular fully connected ...
- 159
1
vote
0
answers
55
views
Prove that a dominating set has minimum cardinality in a "unit interval graph"
I am given the definition of a unit interval graph, e.g. $G = (V, E)$ such that $\forall v \in V$ there is a weight $x_v \in \mathbb{R}$ and nodes $u, w$ has an edge iff $|x_u - x_w| < 1$. I am ...
- 159
1
vote
0
answers
89
views
Solution methods for this Weighted Partial Set Cover-ish problem
Given a set of subsets $S_1, ..., S_N$ of a finite universe $E$ of elements $e_1, ..., e_n$ and mapping of those elements to an integer 'weight' $w_1, ... w_n$, select the subset of subsets which ...
- 313
3
votes
0
answers
58
views
What is the name for this minimal satisfying set covering problem? [duplicate]
Preface
Hello! I have a problem here that's difficult for me to Google, and I don't know if there's a name for it. It feels like a set cover problem of some kind, but I'm very unfamiliar with ...
- 31
1
vote
0
answers
117
views
A Special Case of Set Cover Problem: Covering Nodes of Tree using Paths [closed]
Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s $ is a ...
- 21
1
vote
0
answers
115
views
Variant of "Exact Cover by 3-Set "
Exact cover by 3-sets is 𝖭𝖯-complete:
Instance: Given a finite set $X = \{x_1, x_2, …, x_{3n}\}$ of $3n$ elements and a collection $C = \{(x_{i_1}, x_{i_2}, x_{i_3})\}$ of 3-elements subsets of $X$;
...
- 11
1
vote
0
answers
19
views
Find optimal starting point of recursive search, with solution known
An Exact Cover problem is commonly denoted as a matrix of 0s and 1s. Columns denote requirements, rows denote possible choices. The problem is solved when a set of rows was found such that, using just ...
- 339
1
vote
1
answer
109
views
Trouble to understand the proof of greedy algorithm for set cover
Problem definition: Given a universe $U$ of $n$ elements, a collection of subsets of $U$, $S = \{S_1,..., S_k\}$, and a cost function $c: S \to Q^{+}$. Find a minimum cost subcollection of $S$ that ...
- 294
2
votes
0
answers
117
views
Upper bound on Set Cover Size
I am working on a related Steiner tree problem that I have reduced to Minimum Set Cover, but stumbled across this related problem and got stuck.
Given an universe of $n$ elements $U = \{1,2,\ldots,n\}$...
- 21
2
votes
2
answers
105
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. ...
- 23
1
vote
1
answer
64
views
Efficient cardinality of set overlap relation
Assume that we have a set S of sets s.
Every pair (s,s') in ...
- 177
6
votes
2
answers
203
views
Minimum set cover with incompatible sets
I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously).
To state it more formally:
We have a finite base set $X$ and a family $\...
- 2,322
1
vote
0
answers
38
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
1
answer
86
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 ...
- 305
2
votes
1
answer
2k
views
Counterexample to greedy solution for set cover problem
I am looking for the answer to the exercise 1-6 in "The Algorithm Design Manual" book. it is stated as follows:
1-6. The set cover problem is as follows: given a set of subsets
$S_1,\dots,...
- 123
2
votes
2
answers
335
views
Approximation of Set Cover
I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better ...
- 41
0
votes
0
answers
99
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 ...
1
vote
0
answers
296
views
Is this a hitting set or set cover problem? [closed]
Define a universe $U$ containing $N$ elements. We are given $N$ sets, each of which is a set.
For example, $U = \{1, 2, 3, 4\}$ and
sets
\begin{align}
S_1 &= \{\{1\}, \{2, 4\}\}, \\
S_2 &= \{\{...
- 111
2
votes
1
answer
111
views
Is this a known problem in graph theory?
My basic problem includes a graph where each node $i$ is associated with a weight $c_i$, and the problem is to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$. This ...
- 159
1
vote
1
answer
53
views
Find the n best choices while maximizing value
Given:
A list of slots (A, B, C, ...)
Every slots supports a list of choices (C0, C1, C2, C3...)
Every choice has a value
All slots must be filled with at most n different choices. The sum of the ...
- 121
0
votes
1
answer
69
views
Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?
After removing multi-sets and sets that have elements that don't exist in $S$.
$S$ = $[9,6,7,4,5,1,8]$
$C$ =$[[9,6,7],[4,5],[1,8]]$
Transform the values in $C$ of the shared index values with $S$. ...
- 57
3
votes
1
answer
456
views
Maximum coverage 1/2-approximation algorithm: why does the central lemma hold?
I am looking for an approximation algorithm for the Maximum Coverage problem and a proof of its approximation ratio. As approximation algorithm I use the greedy algorithm which chooses the set that ...
- 33
0
votes
1
answer
40
views
What practical/efficient algorithms exist for minimum weighted set cover problem (MIN-WSCP)?
For TSP there are well known heuristic and approximation solutions which run in low-polynomial time, like Christofides / 2-OPT and so on.
I need a practical, fast algorithm, ideally sub-quadratic ...
- 131
2
votes
1
answer
2k
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....
- 153
1
vote
1
answer
86
views
Selection over combinatorics that satisfies a distribution
I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not.
Here is the problem :
Consider a list of M ...
- 61
3
votes
1
answer
152
views
Upper bound for size of minimal covers of a set
Would appreciate any insight about the following regarding set covers:
Begin with a universe set $X = \{x_1,x_2,...,x_n\}$ and a set $S=\{s_1, s_2,...,s_p\}$ such that each $s_i \subseteq X$ and $\...
2
votes
0
answers
49
views
Boolean matrix / satisfiability problem [duplicate]
Let $M$ be an $m\times n$ matrix with all elements in $\{1,0\}$, $m >> n$. Let $\mathbf{v}_0, \ldots, \mathbf{v}_n$ be the columns of $M$.
I want to find all sets of columns $S = \{\mathbf{v}_{...
- 121
4
votes
1
answer
274
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$ ...
- 464
1
vote
1
answer
212
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 ...
- 11
4
votes
1
answer
2k
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}$ ...
- 143
1
vote
1
answer
445
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 ...
- 175
0
votes
0
answers
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 ...
- 77