Questions tagged [set-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
37
votes
3answers
1k views

Parameterized complexity of Hitting Set in finite VC-dimension

I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...
26
votes
4answers
2k views

Bounded-cardinality bounded-frequency set cover: hardness of approximation

Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets. Example: the case $k = 4$ ...
16
votes
2answers
733 views

Set Cover for Permutation Matrices

Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has ...
15
votes
2answers
1k views

What is the following variation on Set Cover known as?

What is the following variation on set cover known as? Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in ...
15
votes
1answer
1k views

Is the following problem NP hard?

Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer. The goal is to find ...
12
votes
2answers
750 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 ...
11
votes
1answer
562 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-...
11
votes
0answers
349 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 ...
11
votes
0answers
322 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 ...
10
votes
2answers
421 views

Hardness of a subcase of Set Cover

How hard is the Set Cover problem if the number of elements is bounded by some function (e.g, $\log n$) where $n$ is the size of the problem instance. Formally, Let $\mathcal{U}=\{e_1, \cdots, e_m\}$...
10
votes
2answers
417 views

Consequences of lower bounds for $\epsilon$-nets on approximation

Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
10
votes
1answer
2k views

Covering a simple polygon with circles

Suppose I have a simple polygon $S$ and an integer $k$. What are some existing approaches for finding the smallest radius $r$ such that I can cover $S$ with $k$ circles of radius $r$? How about if $...
10
votes
0answers
345 views

Gap hardness of Multi-Dimensional Cover

Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the ...
9
votes
1answer
796 views

Inapproximability of set cover: can I assume m=poly(n)?

I am trying to show that a certain problem is inapproximable by a reduction from set cover. My reduction transforms an instance with ground set of size $n$ and $m$ sets into an instance of my problem ...
8
votes
1answer
278 views

NP-hardness of a Set Cover specialization

Is the following problem NP-hard? Given a set of $N$ real numbers (targets) $x_1,\dotsc,x_N$ and a "trident" defined by two distances $a$, $b$ from the center of the trident, what is the minimum ...
8
votes
0answers
980 views

Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?

This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware. Informal ...
7
votes
1answer
472 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}^* \...
7
votes
1answer
711 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. ...
7
votes
1answer
341 views

expected number of sets generated by greedy set cover ?

I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = \...
7
votes
0answers
617 views

Hardness of Approximation results for Special Set Packing Problem Wanted

Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem? The general Set Packing Problem would be: Given A Collection of ...
6
votes
1answer
189 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 ...
6
votes
1answer
1k views

Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET

There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at http://en.wikipedia.org/wiki/Dominating_set#L-reductions (attributed there to Kann 1992, but seen, for ...
5
votes
1answer
337 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 (...
5
votes
1answer
324 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 ...
5
votes
1answer
1k views

Is there a randomized algorithm for set-cover?

Is there a well-known randomized algorithm for the set cover problem in the literature - such that it has an approximation ratio of $O(\log n)$ or $f$ - where $f$ is the max frequency of an element. ...
5
votes
1answer
239 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 ...
5
votes
1answer
600 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 ...
5
votes
1answer
2k views

Implementation that solves minimum set cover

Does anyone know of any tools that solve the approximate minimum set cover problem? I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about ...
5
votes
0answers
194 views

Can we achieve a better kernel for the Vertex Cover problem on planar graphs?

We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC. My question is, can we do better for planar graphs? It is ...
4
votes
3answers
274 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=...
4
votes
1answer
189 views

Approximating Min-Sum Set Multicover

Approximations for the set multicover problem have been studied (Rajagopalan & Vazirani (section 5)), as have approximations for the min-sum set cover problem (Feige et al.). The greedy heuristic ...
4
votes
0answers
150 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 ...
4
votes
0answers
173 views

Approximation ratio for covering n points in d dimensions

What is best known approximation ratio for the following problem : Given n points in d dimensions , what is the minimum number of axis parallel lines needed to cover them . A line is said to cover a ...
3
votes
1answer
62 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 ...
3
votes
1answer
307 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, ...
3
votes
3answers
387 views

Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
3
votes
1answer
455 views

How efficiently can one find small subcovers for integer intervals?

This question is inspired by one of my professors giving out sequential lecture notes that have a significant amount of overlap :-). What is known about the following problems? Given a set of ...
3
votes
1answer
169 views

bounded outdegree bipartite spanners

Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties : $G'$ ...
3
votes
0answers
50 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 ...
3
votes
0answers
66 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 ...
3
votes
0answers
116 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
votes
0answers
61 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 ...
2
votes
1answer
216 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 $...
2
votes
1answer
871 views

How to approximate minimum clique edge cover

I'd like to take an undirected graph and express it (meaning all of its edges) using only cliques (ideally minimizing their sum cardinality). It's clear that actually finding the minimum solution is ...
2
votes
1answer
654 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 ...
2
votes
0answers
63 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,...
2
votes
1answer
144 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
0answers
98 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:...
2
votes
1answer
294 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 ...
2
votes
0answers
80 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 \...