Questions tagged [set-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
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,...
6
votes
1answer
182 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 ...
0
votes
1answer
61 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 ...
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 ...
11
votes
0answers
348 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 ...
-1
votes
1answer
77 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 ...
0
votes
1answer
376 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 ...
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 ...
1
vote
1answer
98 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$ ...
2
votes
0answers
97 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:...
4
votes
0answers
149 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 ...
2
votes
1answer
618 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 ...
3
votes
1answer
303 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, ...
5
votes
1answer
574 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 ...
2
votes
1answer
288 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 ...
5
votes
1answer
319 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 (...
0
votes
0answers
25 views

Optimizing distribution of load

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 ...
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 \...
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 ...
11
votes
0answers
320 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 ...
1
vote
1answer
92 views

Minimum order of partite in a bipartite graph

I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum ...
5
votes
1answer
236 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 ...
0
votes
1answer
49 views

1-D set cover optimisation with connected subsets

Given a 1-D universe $U$ (e.g. $\mathbb{Z}$) and a set-of-sets $\pmb{S}$, where each element of $\pmb{S}$ is a closed, connected subset of $U$ (e.g. $[a .. b]$ given $ a,b\in\mathbb{Z}$) and $\bigcup\...
7
votes
1answer
468 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}^* \...
12
votes
2answers
738 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 ...
4
votes
3answers
269 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=...
-1
votes
1answer
106 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 ...
11
votes
1answer
556 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-...
2
votes
1answer
215 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 $...
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 ...
1
vote
2answers
220 views

Covering by disjoint sets

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. I'm interested in the approximability of two problems, or in ...
2
votes
0answers
354 views

Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?

Several authors, starting with Slavik, have noted that the classical analysis of the set cover $H_n$ greedy algorithm does not readily extend to the set partial cover problem, where the goal is to ...
5
votes
1answer
323 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 ...
7
votes
1answer
702 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. ...
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 ...
10
votes
2answers
419 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\}$...
0
votes
0answers
182 views

Finding assignment-minimum complete k-partite graph cover

Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs? I'm assuming this problem is NP-...
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 ...
2
votes
1answer
868 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 ...
3
votes
1answer
168 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'$ ...
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. ...
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 ...
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 ...
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 ...
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 = \...
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 ...
3
votes
3answers
385 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 ...
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 ...