Questions tagged [set-cover]
The set-cover tag has no usage guidance.
77
questions
5
votes
0
answers
59
views
W[t]-containment of partial covering problems
I would like to know more about the W[t]-containment of partial covering problems. Especially, I am interested in the question whether Partial Set Cover (Problem Definition at the end of the question) ...
- 81
0
votes
1
answer
60
views
Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover
As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size $k$,...
- 135
2
votes
0
answers
66
views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined.
One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 607
0
votes
0
answers
120
views
Approximate inclusion-Exclusion?
I am trying to understand or find literature on the following problem of approximate inclusion exclusion.
Let $S:=\{A_i\}_{i=1}^{m}$ be a set of $m$ sets. Every intersection of $k$ elements in $S$ ...
- 706
1
vote
1
answer
82
views
Set cover with rewards
I am dealing with the following problem: Given a universe $U$, let $\mathcal{S}$ be a family of subsets of $U$. Each subset $S\in\mathcal{S}$ is associated with a non-negative reward, and each element ...
- 13
0
votes
0
answers
75
views
A Simpler Solution for a special case of the Set Cover problem
We decomposed a simple polygon into many small regions. Then we estimated a visibility polygon of a point by a subset of the small regions. Now I need the minimum set of visibility polygons that can ...
0
votes
1
answer
62
views
Set cover where consecutive sets differ by at most one item [closed]
First I define my version of the set cover problem: We have a collection of sets such as $S_1, \dots, S_m$ where each $S_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of ...
- 230
0
votes
0
answers
73
views
"Fast" approximation algorithm for geometric hitting set of same-height rectangles
In the Geometric Hitting Set problem, we are given a set of $m$ geometric objects and a set of $n$ points in $\mathbb{R}^2$, and we wish to find a small subset of the points that hits all the objects.
...
- 2,143
2
votes
1
answer
76
views
Covering a binary relation as a union of rectangles
Given finite sets $X$ and $Y$ and a subset $R\subset X\times Y$, I want to express $R$ as a union $R=\bigcup_{i=1}^n X_i\times Y_i$ with $n$ as small as possible. Here, each $X_i\subset X$ and $Y_i\...
- 151
4
votes
0
answers
47
views
Minimal partition covering?
I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems.
The problem is:
Start with a set of points $S$ and a target partition of ...
- 141
-2
votes
1
answer
85
views
Set cover with small subsets [closed]
Has the variant of the Set Cover problem where each set is of size at most $d$, for some given $d$, been studied? Is it polynomial-time solvable for $d=2$ and NP-hard for $d=3$ like SAT?
3
votes
1
answer
143
views
CNF encoding of set cover - NExpTime-completness
Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true.
I ...
0
votes
1
answer
452
views
What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?
Let $X$ be the universe of elements, $F$ a collection of subsets $S \subseteq X$, each with an associated cost. The goal is to find a subcollection $C \subseteq F$ of minimum total cost which covers $...
2
votes
1
answer
106
views
Can the Banach-Tarski paradox be "realized" by floating-point round-off?
The Banach-Tarski paradox says that
a ball in $\mathbb{R}^3$ can be partitioned into a finite number of pieces, whose rearrangement has a larger volume than the original.
It occurred to me that it ...
- 3,713
3
votes
0
answers
76
views
Hardness of Approximation of Set Cover with Growing Size Bound
I'm considering the minimum set cover problem with the constraint that each set contains at most $k$ elements.
Here, $k$ depends on the size of the universe.
For example, $k$ may equal $\log n,\sqrt ...
- 101
2
votes
0
answers
76
views
Hardness result or reference for a set partition problem
I'm wondering if the following problem is (or has been proven to be) NP-Complete.
Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$.
Accept iff: there exists $\{a_i,...
- 101
6
votes
1
answer
219
views
Minimal generator for a set of sets
Is this a known problem?
Given a set of sets $S$ find a set of sets $B$ s.t. each set in $S$ can be obtained through unions of some sets in $B$. The set $S$ is already a solution but the objective is ...
- 1,312
0
votes
1
answer
86
views
Polynomial approximation algorithm for set cover with assumption
We want to cover $n$ elements with some sets from $S_1, …, S_m$ (classical set cover).
We furthermore suppose that any element belongs to at least $k$ sets and want to find a set cover with cardinal ...
- 129
2
votes
1
answer
163
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 ...
- 23
11
votes
0
answers
388
views
Error in paper "Some NP-complete geometric problems"?
The paper in question:
M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems .
This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
- 275
-1
votes
1
answer
85
views
Restricted Universe Exact Cover
Apologies for a simple question - I am a beginning graduate student in TCS.
Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and ...
- 15
0
votes
1
answer
1k
views
Definition of k-set cover
I'm trying to understand the sparsification lemma by Impagliazzo, Paturi and Zane (IPZ) (from this article) and in their proof they reduce the k-SAT problem to the k-set cover problem. But their ...
3
votes
1
answer
77
views
Complexity of Finding Optimal Synergistic Set Packings
Motivation: While developing tools for fast execution of machine learning workflows, we realized that many workflows require intermediate results -- sometimes we should cache these results, and ...
- 133
1
vote
1
answer
110
views
Set cover by alternative of sets
I had this question when looking at problem C on this morning's code jam:
Suppose you have a set $S$ and $N$ pairs of subsets $\{S_i^0, S_i^1\}$, $S_i^j\subset S.$
Does there exist a cover of $S$ ...
- 213
2
votes
0
answers
114
views
Alternative Set Cover Algorithm With Doubling
I remember that I saw once an alternative to the greedy set cover algorithm that works as follows:
Assign weight 1 to every element in the universe. Repeat steps 2 and 3 until the universe is covered:...
- 121
4
votes
0
answers
191
views
Approximating set cover when it is known that an exact set cover exists
Suppose $U = \{1, 2, \cdots, n\}$ is a universe and $\mathcal S = \{S_1, S_2, \cdots, S_m\}$ is a collection of sets such that each set contains exactly $c$ elements, where $c$ is a constant.
In this ...
- 227
2
votes
1
answer
1k
views
Partial cover approximation
We have a set of elements $E=\{e_1, e_2, \ldots, e_m\}$, and $n$ subsets of $E$: $S_1, S_2, \ldots, S_n$ The union of those subsets is $E$, and each subset $S_i$ has a non-negative weight $w_i$.
The ...
3
votes
1
answer
438
views
What is the reverse of greedy algorithm for setcover?
A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, ...
- 175
5
votes
1
answer
1k
views
Is there an approximation algorithm for MAX k DOUBLE SET COVER?
Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define ...
- 2,143
2
votes
1
answer
545
views
Counting distinct set covers
I'm given a universal set $N = \{1, 2, \dots, n\}$, a family of sets $\mathcal{F} = \{ S_1, S_2, \dots, S_m \}$, $S_i \subseteq N$, and I need to count the number of distinct ways to cover the ...
- 143
5
votes
1
answer
667
views
Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?
Given:
A bipartite graph G=(U,V,E)
Integers n and k.
Decision Problem:
Is there a subset of U of size k that has at most
n neighbours?
I am trying to figure out whether this problem is NP-hard (...
- 153
0
votes
0
answers
26
views
Optimizing distribution of load
I want to run $k$ programs distributed on $N$ machines. Because of resource constraints, a machine can have at most $p$ of the $k$ programs installed. To have a balanced system, I can install each of ...
- 101
2
votes
0
answers
91
views
Variant of set cover problem with symmetric difference instead of union? [duplicate]
I am wondering if this problem has been studied, and in particular if there is an algorithm for it.
Consider a universe $\mathcal U$ and a set $A \subseteq U$, and a family of sets $\mathcal F \...
- 121
3
votes
0
answers
72
views
Average number of sets given by greedy set cover? Is it uniform distribution?
We're covering the whole random universe $U$ of size $m$ with random sets $S_{1},\dots S_{n}$. I know that greedy set cover gives us a number between size of the minimal set cover and size of the ...
- 31
4
votes
0
answers
165
views
Set cover approximation ratio as a function of m (number of sets)
Feige's well known result (and more recent results) show that set cover cannot be approximated within a factor of $(1 - o(1)) \ln n$, where $n$ is the number of variables. What if we want an ...
- 3,488
16
votes
0
answers
481
views
a geometric variant of k-medians. NP-hard or in P?
The following problem is a special case of k-medians. Is it NP-hard? Is it in P?
Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.
Output: a set ...
- 9,595
1
vote
1
answer
105
views
Minimum order of partite in a bipartite graph
I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum ...
- 113
5
votes
1
answer
308
views
Set cover in which some pairs of sets are forbidden
I'm trying to find an approximation algorithm for a variant of the weighted set cover problem. However, this variation doesn't seem to let me apply the traditional set cover arguments for an ...
- 312
0
votes
1
answer
56
views
1-D set cover optimisation with connected subsets
Given a 1-D universe $U$ (e.g. $\mathbb{Z}$) and a set-of-sets $\pmb{S}$, where each element of $\pmb{S}$ is a closed, connected subset of $U$ (e.g. $[a .. b]$ given $ a,b\in\mathbb{Z}$) and $\bigcup\...
- 103
7
votes
1
answer
635
views
Parameterized complexity of Exact Cover
Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^* \...
- 213
12
votes
2
answers
1k
views
What is this variant of set cover problem known as?
Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$.
An incremental ...
- 221
5
votes
3
answers
429
views
Variation on partial Set Cover with penalties
I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem:
Input: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup B=...
- 171
-1
votes
1
answer
127
views
Combinatorial algorithm for load balancing
I have a problem that can be solved with linear programming, but I'm hoping there's a combinatorial algorithm for this (even approximation is fine).
This is basically a load balancing problem using ...
- 1
11
votes
1
answer
886
views
Set Cover with bounded intersection size
So, the set cover problem is trivial if none of the candidate sets intersect eachother.
However, what if the size of the intersection for any pair of candidate sets was at most 1? Is this problem NP-...
- 119
2
votes
1
answer
287
views
Set cover with budget on sets
I am wondering if this is a studied variant of the Set Cover problem.
We are given a universe $X$, a collection of sets $S = \{S_1, ..., S_m\}$ and integers $c_i$. We want to cover all elements in $...
- 21
3
votes
0
answers
70
views
Do there exist "odd times" cover problems and what do we know about their approximability?
I am currently investigating a problem which can be formulated as a cover problem, in which real intervals have to be covered an odd number of times by integers.
My question is just, if anybody has ...
- 306
2
votes
2
answers
645
views
Covering by disjoint sets
We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$.
I'm interested in the approximability of two problems, or in ...
- 9,428
2
votes
0
answers
424
views
Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?
Several authors, starting with Slavik, have noted that the classical analysis of the set cover $H_n$ greedy algorithm does not readily extend to the set partial cover problem, where the goal is to ...
- 113
5
votes
1
answer
505
views
Worst case ratio between minimum clique cover and maximum independent set
The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices ...
- 916
7
votes
1
answer
987
views
Approximating Max-Coverage when the elements need to be covered multiple times
In the set multicover problem we are given a set N of n elements and a set S of m subsets of N. Additionally, each element has a coverage requirement, i.e. the number of times it has to be covered. ...
- 213