# 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.

132 questions
Filter by
Sorted by
Tagged with
99 views

### Problem of constructing binary sequence with least possible 1s under given constraint

You are given a binary pattern p. Problem is to construct a binary sequence of length n such that by sliding p over our sequence there is always at least one position where two 1s align (one in the ...
63 views

### will it help to find the optimal solution to set cover problem if all exact-covers of the same problem were found

I have a set cover problem in the real world, it is a unicost set cover problem, with many subsets(around 10~30 million subsets, yes, no mistake here). Due to the nature of the problem in real world, ...
1 vote
38 views

### Set cover variation: disjoint covers for all but one element

In the classical set cover problem, we are given the set $U$ of elements $\{1, \dots, n\}$ and a collection $C$ of some subsets such that their union is the whole set. Now, I will introduce the first ...
• 111
1 vote
59 views

### Choose edges in fully connected weighted graph that minimize sum of weights

I was looking at the Advent of Code 2023 day 11 problem and misread it to think that the question ended up asking something akin to what's below (after transforming the positions of the "galaxies&...
• 113
24 views

130 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
68 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
1 vote
53 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
26 views

• 2,522
1 vote
49 views

• 123
424 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
102 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
353 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
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
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
76 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$. ...
535 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 ...
42 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
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
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 ...
162 views

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 51 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
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$ ...
### 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 ...