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

102 questions
Filter by
Sorted by
Tagged with
34 views

### Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm

I am trying to solve the Budgeted Maximum Coverage Problem. I have read and implemented the greedy and modified-greedy methods to solve it, as proposed by Khuller. Both are approximation algorithms. ...
22 views

### Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
103 views

64 views

### Triangles covering all vertices of a tri-partite graph

This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers. I'm designing fictional fruits. Each fruit has three attributes; color, taste ...
113 views

42 views

44 views

### Weighted Set Cover Problem Minimizing Average Weight

In the traditional weighted set cover problem, we aim at minimizing the sum of the weight of the selected sets. Is there any problem/literature that aim at minimizing the average weight of the ...
67 views

### Clarification on NP-hardness and hardness of approximation results for set cover?

I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements. I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it ...
185 views

### Approximation algorithm for weighted set cover, using multiplicative weights

It is known that the problem of fractional set cover can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ...
128 views

### Solving the Size-Constrained Weighted Set Cover Problem

I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the ...
104 views

### Minimal edge cover of the hypergraph

We know that minimal edge cover for the normal graph is polynomial time solvable. Is it also true for hypergraph?
129 views

### set cover to edge cover

I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I ...
621 views

### set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
2k views

### Given a set of intervals on the real line, find a minimum set of points that “cover” all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
1k views

199 views

### An exact solution for biclique vertex-cover problem on a bipartite graph

The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs). It has been shown that "Biclique Vertex-...
There are $n$ points in a plane. The decision problem is to identify whether there exists a set $S$ of $k$ or less points from the $n$ points such that all $n$ points are at most $d$ distance from ...