Questions tagged [set-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
53 views

Minimum number of sets of points

During my work I've encountered this problem: $G = \{(x_i,y_i,z_i)\}_{i=1}^{n}$ is a group of points in space ($\forall i \;\; x_i,y_i,z_i \in \Bbb R$) and $ d \in \Bbb R^+$ is a constant. Divide $...
2
votes
2answers
43 views

Growing a set given constraints

I am trying to solve the following: Given a set $S_0$, find min $|S|$ where $S_0 \subseteq S$ subject to: $\forall s \in S$ $\exists$ $s_a, s_b \in S $ $|$ $ ( s_a \neq s, s_b\neq s ) \land ( s = ...
1
vote
1answer
65 views

Minimum covering problem formulation

Shouldn't I post this question on mathematics.stackexchange.com? Let be an airlaine company which has to affect its aircrew to several flights. We group som flights in subset, every flights of a ...
1
vote
1answer
466 views

What is Unique Coverage Problem?

I am trying to understand the problem statement and the approximation algorithm for the Unique Coverage Problem from these notes. I have refined the question based on the comments provided. Thanks to ...
3
votes
1answer
142 views

Clarification on the inapproximability of set cover

I'm trying to understand the inapproximability of the minimum set cover problem. The wikipedia page states that it is hard to approximate within a factor of $(1-o(1))\ln n$ and that $n$ refers to the ...
3
votes
1answer
128 views

NP-hardness of maximum set cover with even/odd coverage requirement

Given universal set $U=X \cup Y = \{x_1, \ldots, x_{n_1} \} \cup \{y_1, \ldots, y_{n_2}\}$ where $X \cap Y = \emptyset$ and sets $\mathcal{S}=\{s_1, \ldots, s_m\}$ such that $s_i \subseteq U$ for all $...
0
votes
1answer
249 views

Is this a proof that SET COVER is not an NP-hard problem?

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows: Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = \{...
2
votes
1answer
54 views

Solution to a Np-hard problem and its relevance to a dual LP

From The design of APX algorithms book by David P. Williamson and David B. Shmoys, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual): Let $y^*$ be ...
1
vote
1answer
421 views

Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm

From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL_G$) and if ...
1
vote
1answer
173 views

Another version of the online set cover problem?

Here is a note about online set cover problem: we are initially given the $m$ sets, but we do not know which elements they contain. At any time $t$, we get a new element $e_t$ and learn which sets ...
3
votes
2answers
625 views

Is greedy algorithm the best algorithm for set cover problem?

Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem. I am a bit confused by this theorem. As we know, greedy algorithm is $(\ln n+...
11
votes
1answer
240 views

Finding a minimal cover of a subset of a finite cartesian product by cartesian products

Given a subset of a cartesian product $I \times J$ of two finite sets, I wish to find a minimal cover of it by sets which are cartesian products themselves. For example, given a product between $I=\{...
2
votes
1answer
95 views

I want to figure out whether my problem described below is reducible to the set cover problem

I have a collection of non-empty sets $S_i$, where $1 \le i \le n$, which are constructed from elements of a universe $U$. I need an algorithm that gives me a set $T$ of minimum cardinality ($T \...
1
vote
1answer
37 views

How can I convert a list with duplicates into a set for a reduction to the set cover problem?

I'm trying to come up with a reduction for a problem whose description is more or less identical to the first problem given here. Here's a condensed version of the problem: You're given a collection ...
6
votes
1answer
60 views

Hardness of a problem related to set cover

Suppose $C_1, \ldots, C_m$ are subsets of $\{1, \ldots, n\}$. The goal is to find the smallest subcollection of $C_1, ..., C_m$ such that each element of $\{1, \ldots, n\}$ appears at least $k$ times ...
3
votes
1answer
834 views

Greedy algorithm for Set Cover problem - need help with approximation

I want to approximate how close is the greedy algorithm to the optimal solution for the Set Cover Problem, which I'm sure most of you are familiar with, but just in case, you can visit the link above. ...
2
votes
1answer
72 views

Reduction from a further constrained problem

If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard? Generally, this is probably not the case. For ...
1
vote
2answers
730 views

How to enumerate minimal covers of a set

I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$. What is the best algorithm for ...
7
votes
1answer
1k views

Proving NP-hardness of strange graph partition problem

I am trying to show the following problem is NP-hard. Inputs: Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph Output: Partition of $G$, $G_p=(V,E_p)$ obtained ...
1
vote
1answer
162 views

Proving NP hardness of maximum sum of means of a partition into k sets

I am trying to show the following problem is NP-hard and would like some help. Inputs: Integer $k$, and unordered set of $N$ numbers, $O$ Output: the $\max \sum\limits_{S_i \in S} \...
3
votes
1answer
151 views

Maximum minimal set coverage

Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq \...
1
vote
1answer
599 views

Set cover problem with constant size subset

Consider a variation of the set cover problem in which the size of the subsets is no larger than a constant $k$. Is this variation still NP-hard?
5
votes
1answer
318 views

Transition coverage for a DFA

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where ...
2
votes
1answer
486 views

Finding an instance of an n-element set cover

Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter ...
5
votes
1answer
2k views

Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers

I have the following problem, which seems to be similar to Set Cover. We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$). We're also given a set $S$ of subsets (e.g., $S=\{\{1\...
2
votes
1answer
112 views

Enumerating all set covers when knowing one set at least

I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$. Then I have a query $Q=(s, k)$, where $s \in P(S) - \{\emptyset \cup S\}$ and $ 1 < k \...
6
votes
1answer
261 views

Time Complexity of a selection problem

I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem. [Assuming operations on integers take $O(1)$ time] We are Given $m$ sets, ...
16
votes
1answer
218 views

Transforming an arbitrary cover into a vertex cover

Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$. I have furthermore a set $C$ of points where each point $c \in C$ is contained ...
6
votes
2answers
6k views

Algorithm to return largest subset of non-intersecting intervals

I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals. i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ ...