Skip to main content
11 votes

What are the real world applications of set cover problem?

Set-cover heuristics are used in random testing ("fuzz testing") of programs. Suppose we have a million test cases, and we're going to test a program by picking a test case, randomly modifying ("...
D.W.'s user avatar
  • 162k
7 votes
Accepted

Counterexample to greedy solution for set cover problem

Usually the set cover problem is formulated such that the quantity to be minimized is the number of sets one picks rather than the sum of the numbers of elements of the sets picked. Unfortunately, ...
Watercrystal's user avatar
  • 1,526
5 votes

What are the real world applications of set cover problem?

Not sure if this is a real-world problem – solving sudokus can be reduced to an exact cover problem (note that exact cover is related to set cover, but not the same). You can find similar explanations ...
user172818's user avatar
5 votes
Accepted

Is 'double max-$k$ vertex-cover' NP-hard?

It was easier for me to show that the $k$-clique problem is a special case of this problem. On an input graph $G$ and an integer $k$, the this special case is defined by $G$,$k$,$t$, with $t=\binom{...
dave's user avatar
  • 628
5 votes
Accepted

Vertex cover algorithms for directed graphs?

Thanks for the edit! This isn't vertex cover; it's something different. There are simple algorithms for this problem. Decompose the graph into a dag of strongly connected components. (The dag is ...
D.W.'s user avatar
  • 162k
5 votes
Accepted

Clarification on the inapproximability of set cover

The hardness proof appears in an earlier paper of Moshkovitz, The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover; Dinur and Steurer proved a version of the Projection ...
Yuval Filmus's user avatar
5 votes
Accepted

maximum coverage version of dominating set

The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least ...
Juho's user avatar
  • 22.6k
4 votes
Accepted

Is the exact cover problem NP-hard when there is a restriction on the size?

Yes, it is still NP-hard. In fact, it remains hard even if you replace $\log_2 n$ with the constant 3. This follows by reduction from 3-dimensional perfect matching. 3-dimensional perfect matching ...
D.W.'s user avatar
  • 162k
4 votes

What are the real world applications of set cover problem?

By far the most relevant, large size, important application of set covering is in personnel shift planning (mainly in large airline companies). There, elements to be covered are the single shifts (or ...
Fabio Schoen's user avatar
4 votes
Accepted

Grid covering by rectangles

Thanks to j_random_hacker's hint, I've found a solution to reduce Vertex Cover to the Grid Problem: We make a $|E|$-by-$|V|$ grid of 3-by-3 blocks, i.e. a $3|E|$-by-$3|V|$ grid, with vertices ordered ...
Yann's user avatar
  • 291
4 votes
Accepted

Hardness of approximating Minimum Cardinality Exact Cover

Suppose that we are given an instance of EXACT 3-COVER (in which every set contains 3 elements) with $m$ sets on $n$ elements; EXACT 3-COVER is known to be NP-complete. Create a new instance in which ...
Yuval Filmus's user avatar
4 votes
Accepted

Minimum set cover with incompatible sets

Your problem can be stated as a minimum weight maximal independent set problem. Construction: Construct a bipartite graph $G = (L,R,E)$, where the right partition $R$ corresponds to $\mathcal{R}$ and ...
Inuyasha Yagami's user avatar
4 votes
Accepted

Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm

Absolutely they can. The approximation algorithms give a formal guarantee that the solution won't be too bad and they quantify what this means whereas with a metaheuristic such as GA all bets are off. ...
Juho's user avatar
  • 22.6k
3 votes
Accepted

Set cover problem with sets of size 2

This is exactly the edge cover problem, which can be solved in polynomial time by finding a maximum matching. Then, for each unmatched vertex, add an arbitrary edge containing that vertex. In fact, ...
David Richerby's user avatar
3 votes
Accepted

Is this variant of set cover NP-complete?

As quicksort comments, you can convert any set cover instance to your special case by adding dummy elements. Take a large enough pool of dummy elements, and put all of it into a new set $S_1$. Then ...
Yuval Filmus's user avatar
3 votes
Accepted

NP-hardness of maximum set cover with even/odd coverage requirement

One can rephrase your question as follows: Given a matrix $A$ and a vector $b$ over $GF(2)$, find a vector $x$ of weight $k$ such that $|Ax-b|$ is as small as possible. A very similar problem was ...
Yuval Filmus's user avatar
3 votes
Accepted

Minimum number of shopping trips for a group of people to buy presents for each other

This problem is NP-hard. To show this, I will first reformulate this (optimization) problem into a decision problem. Then, I reformulate that problem into an equivalent one, from which it is fairly ...
Discrete lizard's user avatar
  • 8,303
3 votes

Vertex cover algorithms for directed graphs?

The problem you're describing sounds more like a Dominating Set style problem to me (vertices covering vertices, Vertex Cover is vertices covering edges), but because you allow the dominating vertex ...
Luke Mathieson's user avatar
3 votes
Accepted

Probability of randomly designated subsets cover the universe

There is no polynomial-time algorithm that computes an exact solution (i.e. the probability expressed as a ratio of two nonnegative integers $a/b$) to your problem unless $\textbf{P} = \textbf{NP}$. I ...
quicksort's user avatar
  • 4,262
3 votes

Is this variation of set-cover NP-hard to approximate?

Your first problem is a classical NP-hard problem known as maximum coverage. The greedy algorithm gives a $1-1/e$ approximation, and this is tight (assuming P≠NP). Your second problem is a special ...
Yuval Filmus's user avatar
3 votes
Accepted

Minimal hitting set with respect to set inclusion from a book "Parameterized Complexity Theory"

It seems you are confusing the terms minimal and minimum. The Hitting set problem is to find a hitting set of minimum cardinality, not a minimal set. A set $S$ is called minimal with respect to some ...
Discrete lizard's user avatar
  • 8,303
3 votes
Accepted

Hitting Set Problem with non-minimal Greedy Algorithm

The greedy algorithm always finds a minimal set (inclusion-wise). However, it does not necessarily find a minimum one. So what does minimal and minimum mean, you might ask. Minimal set in a family of ...
Narek Bojikian's user avatar
3 votes

Selection over combinatorics that satisfies a distribution

Consider the following special case where for each element $i$ the table contains the constraint $\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears ...
Narek Bojikian's user avatar
3 votes
Accepted

Maximum coverage 1/2-approximation algorithm: why does the central lemma hold?

Let $S_{O_1},\ldots,S_{O_k}$ be an optimal solution, and let $O = S_{O_1} \cup \cdots \cup S_{O_k}$. At the $i$'th iteration, suppose that the elements covered by the sets chosen the algorithm form ...
Yuval Filmus's user avatar
3 votes

Approximation of Set Cover

Dinur and Steurer [1] showed that assuming $P \neq NP$, there is no polynomial time algorithm which approximates set cover by a $(1-\epsilon)\ln(n)$ factor, for any constant $\epsilon > 0$. [1] ...
user3209423940248's user avatar
3 votes

Approximation of Set Cover

Clarification: When we say $\ln n$ is the best possible approximation for the set cover problem, we mean it for a general instance of the set cover. That is, there are set cover instances in which an ...
Inuyasha Yagami's user avatar
3 votes
Accepted

Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?

Solution 1 Given an instance $\Pi$ of set cover with non-empty subsets of size at most 2, consider two instances of set cover with subsets of size exactly 2: $\Pi'$ contains all subsets in $\Pi$ of ...
Yuval Filmus's user avatar
3 votes

Lower Bounding Set Cover's Approximation Ratio

Yes. You should read the lower bound as: there exists an instance with $m$ items such that $\frac{G}{\text{Opt}} \ge \log m - \log \log m - 0.31$.
Steven's user avatar
  • 29.5k
2 votes

What is Unique Coverage Problem?

Let's go over your questions one by one: (1) Your definition of Unique cover is wrong. Given a set system $\mathcal{S}$, the goal is to find a subset $\mathcal{S}' \subseteq \mathcal{S}$ which ...
Yuval Filmus's user avatar
2 votes

Minimum number of shopping trips for a group of people to buy presents for each other

I can see how to reduce this problem to Graph Colouring, which gives you a tool for solving the problem (for small instances!), but not yet how to reduce in the other direction (which would establish ...
j_random_hacker's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible