Questions tagged [set-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
40 views

Minimal partition covering?

I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems. The problem is: Start with a set of points $S$ and a target partition of ...
-3
votes
0answers
86 views

The max-min resource assignment problem

I am wondering if there are any results for the following max-min assignment problem: Given n machines C = {C$_1$, C$_2$... C$_n$} with the k-th machine has power C$_k$. There are m tasks T = {T$_1$, ...
-2
votes
1answer
76 views

Set cover with small subsets [closed]

Has the variant of the Set Cover problem where each set is of size at most $d$, for some given $d$, been studied? Is it polynomial-time solvable for $d=2$ and NP-hard for $d=3$ like SAT?
1
vote
0answers
76 views

Hardness of Approximation of Continuous Metric k-Median

First let me describe the metric $k$-median problem. Definition (Metric $k$-Median): Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ ...
0
votes
0answers
47 views

what is the LP gap of this particular non metric facility location problem in planar graphs?

Suppose I have a facility location problem with all service costs 0 (or infinity (in particular service costs are not metric)) such that the edges $ij$ for which facility $i$ can service client $j$ ...
3
votes
1answer
112 views

CNF encoding of set cover - NExpTime-completness

Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true. I ...
0
votes
1answer
119 views

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

Let $X$ be the universe of elements, $F$ a collection of subsets $S \subseteq X$, each with an associated cost. The goal is to find a subcollection $C \subseteq F$ of minimum total cost which covers $...
2
votes
1answer
97 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 ...
3
votes
0answers
59 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
67 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
201 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
67 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
145 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
367 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
82 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
683 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
66 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
101 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
105 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
158 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
898 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
342 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
776 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
438 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
440 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
26 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
84 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
70 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
122 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
328 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 set ...
1
vote
1answer
93 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
266 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
52 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
518 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
894 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
306 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
111 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
708 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
235 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 ...
2
votes
2answers
283 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
383 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
398 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
796 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
461 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
472 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
190 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
195 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
908 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
173 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'$ ...