The set-cover tag has no wiki summary.
2
votes
1answer
119 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
123 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'$ ...
1
vote
1answer
236 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. ...
5
votes
0answers
133 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
128 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
336 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
232 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 = ...
9
votes
1answer
733 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
128 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 ...
4
votes
1answer
206 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 ...
1
vote
1answer
221 views
Worst-case asymptotic-complexity of the Set-cover problem?
What's the worst-case asymptotic-complexity of the Set-cover problem in Big O notation?
I've been developing some novel techniques to try and solve this problem but am having trouble finding the ...
4
votes
0answers
126 views
Can we achieve a better kernel for the Vertex Cover problem on planar graphs?
We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC.
My question is, can we do better for planar graphs? It is ...
5
votes
0answers
232 views
Hardness of Approximation results for Special Set Packing Problem Wanted
Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem?
The general Set Packing Problem would be:
Given A Collection of ...
10
votes
1answer
429 views
Covering a simple polygon with circles
Suppose I have a simple polygon $S$ and an integer $k$. What are some existing approaches for finding the smallest radius $r$ such that I can cover $S$ with $k$ circles of radius $r$? How about if ...
8
votes
1answer
383 views
Inapproximability of set cover: can I assume m=poly(n)?
I am trying to show that a certain problem is inapproximable by a reduction from set cover. My reduction transforms an instance with ground set of size $n$ and $m$ sets into an instance of my problem ...
1
vote
0answers
162 views
Upper bound for set cover with respect to m that is better than trivial when $n \ge 3m$
Does anyone know of an upper bound for Set Cover $(\mathcal{U}, \mathcal{S}, k)$ with respect to $m=|\mathcal{S}|$ that is better than trivial when $n =|\mathcal{U}|$ is at least $3m$?
(Set cover).
...
5
votes
0answers
476 views
Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?
This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware.
Informal ...
10
votes
0answers
222 views
Gap hardness of Multi-Dimensional Cover
Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the ...
12
votes
2answers
462 views
Set Cover for Permutation Matrices
Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has ...
9
votes
2answers
294 views
Consequences of lower bounds for $\epsilon$-nets on approximation
Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
0
votes
2answers
1k views
Dynamic programming algorithm for NP-complete problem
Hello everybody here is a problem i have approximated but would like to hear your opinion about. Perhaps someone finds a better solution than me :)
Given a Graph G with undirected edges:
Divide it ...
20
votes
4answers
716 views
Bounded-cardinality bounded-frequency set cover: hardness of approximation
Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.
Example: the case $k = 4$ ...
28
votes
2answers
735 views
Parameterized complexity of Hitting Set in finite VC-dimension
I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...
10
votes
2answers
406 views
What is the following variation on Set Cover known as?
What is the following variation on set cover known as?
Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in ...
