9

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 ("mutating") it by flipping a few bits, and running the program on the modified test case to see if it crashes. We'd like to do this over and over again. If we do ...


6

Put each of the $k-1$ greatest numbers in their own set, and the remaining numbers all together in the $k$th set. This linear-time algorithm can be proved correct by using the following (non-strictly) improving moves to reach the specified optimal solution from any other. Given two numbers $a<b$ with $a\in S_i$ and $b\in S_j$ and $\lvert S_i\rvert\le\...


5

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 Games Conjecture, thus completing the NP-hardness proof. Moshkovitz clearly states that $n$ is the size of the universe, and she also assumes that the number of ...


5

This is called the "Interval Scheduling" problem in the book [1]. The greedy algorithm, along with an example, is as follows (please find the correctness proof in the book mentioned above): sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$. while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}...


5

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 sometimes called "the metagraph".) Each source vertex in the dag corresponds to a SCC that has no edges coming into it from outside; for each such SCC, pick one ...


5

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{k}{2}=k(k-1)/2$. Observe that some $V'\subseteq V$ of size $k$ is a clique in $G$ if and only if the set $V'$ covers at least $\binom{k}{2}$ edges twice. ...


5

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 here. Some fast solvers directly use Knuth's dancing links to solve sudokus, which is usually much faster than naive backtracking. However, the fastest solvers ...


5

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 by Lamprou, Sigalis and Zissimopoulos [1] and Khuller, Purohit and Sarpatwar [2]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan [3]...


4

Hine: Given an instance of set cover, add $k-1$ copies of the set $\{1,\ldots,n\}$.


4

You have shown that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then the greedy algorithm finds $k$ sets which cover at least $n/2$ elements, and so at most $n/2$ elements are left uncovered. You can prove by induction that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then for each $t$, the ...


4

Hardness Your problem might be called "maximum minimal set cover". In particular, your problem feels like it might be related to minimum maximal matching, which is NP-hard. If you wanted to try to prove NP-hardness, you might try to see if you can find a reduction from minimum maximal matching. Algorithms Your problem can be expressed as an instance of ...


4

The problem is NP-hard for $k\ge3$. It has a straightforward reduction from the 3-dimensional matching problem.


4

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 is the following problem: Input: disjoint sets $X,Y,Z$ such that $|X|=|Y|=|Z|$; a set $T \subseteq X \times Y \times Z$ Question: does there exist a perfect ...


4

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 as columns $\{v_1,\dots,v_{N_1}\}$ and edges ordered as rows $\{e_1,\dots,e_{N_2}\}$. We'll construct rectangles on this grid (the drawing below will help a ...


4

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 each element is replicated $t$ times, each of the original $m$ sets contains each copy of each element, and additionally all $tn$ singletons are available. When ...


4

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, this means that your example does not prove that the given greedy algorithm fails to find optimal solutions as the cover it produces consists of 3 sets, which is ...


4

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 the left partition $L$ corresponds to $X$. An edge $(u,v) \in E$ iff an element $u$ is contained in the set $v$. Let $G'$ be the updated graph obtained by ...


4

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. Really, the only guarantee you have with GA is that the solution is valid, but that's it. Your best bet is to just implement the GA and give it a try. Much ...


3

Any linear program has a dual linear program, whose constraints are in one-to-one correspondence with the variables of the primal program. Under mild conditions, the optimal value of the dual program coincides with the optimal value of the primal program, and certain conditions known as complementary slackness are satisfied by any pair of optimal solutions. ...


3

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 shown to be NP-complete by Stadnicki on cstheory: Given a matrix $A$ and a vector $b$ over $GF(2)$, does there exist a vector $x$ of weight at most $k$ such ...


3

The result you quote, due to Feige, has actually recently been improved by Dinur and Steurer (based on earlier work of Moshkovitz), who showed that unless $P = NP$, there is no polynomial time $(1 - o(1))\ln n$-approximation algorithm for set cover. This result states that if all you care about is the worst case approximation ratio, then you cannot ...


3

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 add subsets of $S_1$ to the other sets to satisfy your cardinality condition, taking care to leave some of them out. Every solution has to take $S_1$, and ...


3

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 to be at any distance from the dominated vertex, the problem becomes much easier. I believe the problem can in fact be solved in (near) linear time (in the ...


3

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 single flights), and sets are legal combinations of work/no work schedules. These easily go to millions or even billions of variables, as the number of ...


3

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, if all you want to know is whether there's an edge cover of size at most $k$, you don't need to construct the cover: the size of a minimum edge cover is $M ...


3

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 will show that such an exact solution would provide a polynomial time algorithm for set-cover. Let $(U, S \subseteq \mathscr{P}(U), k)$ be an instance of set-...


3

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 case of set cover. Indeed, take any instance of set cover, and add to it the set $S$ itself. If the optimal solution for the set cover instance is $M$, then the ...


3

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 property (in this case, being a hitting set) if there exists no strict subset $T$ of $S$ (i.e. $T\subsetneq S$) that also satisfies that property. On the ...


3

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 at least once. This problem is called the set covering problem, where you have to output whether there is a subset of $l$ sets in the input that covers all the ...


3

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] https://arxiv.org/pdf/1305.1979.pdf


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