# 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
Filter by
Sorted by
Tagged with
21 views

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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
25 views

1 vote
38 views

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 ...
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
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 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 ...
1 vote
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 ...
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$. ...
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 ...
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 ...
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....
1 vote
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 ...
152 views

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$ ...
1 vote
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 ...
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}$ ...
1 vote