# Questions tagged [set-cover]

The tag has no usage guidance.

77 questions
Filter by
Sorted by
Tagged with
96 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$ ...
1 vote
69 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 ...
37 views

### Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
66 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 ...
50 views

### Bound on Set Cover size between multiple families

I am working on a related Steiner tree problem that I have reduced to Minimum Set Cover, but stumbled across this related problem and got stuck. Given an universe of $n$ elements $U = \{1,2,\ldots,n\}$...
55 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 ...
69 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. ...
74 views

104 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 ...
67 views

213 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 ...
79 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 ...
159 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 ...
379 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 ...
84 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 ...
952 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 ...
71 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 ...
1 vote
107 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$ ...
107 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:...
167 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 ...
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 ...
404 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, ...
980 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 ...
508 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 ...
619 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 (...
26 views

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 ...
91 views

565 views

125 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 ...
795 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-...
266 views