11

The case of $m = c \log n$ is in $n^{O(c)}$ time as noted by Yuval, but also note for $k = O(1)$ you can solve the problem in $O(n^k \cdot m)$ time (polynomial time) by exhaustive search. Assuming the Strong Exponential Time Hypothesis (that CNF-SAT on formulas with $N$ variables and $O(N)$ clauses requires at least $2^{N-o(N)}$ time), these two time bounds ...


11

When $m = O(\log n)$, you can use dynamic programming to find the optimum in polynomial time. The table contains Boolean-valued cells $T_{\ell,X}$ for each $\ell \in \{0,\ldots,k\}$ and $X \subseteq \mathcal{U}$, indicating whether there are $\ell$ sets which cover the elements in $X$. When $m = O(\sqrt{n})$, say $m \leq C\sqrt{n}$, the problem remains NP-...


10

It's NP-complete by a reduction from cliques in graphs. Given an arbitrary graph $G$, construct a bipartite graph from its incidence matrix, by making one side $U$ of the bipartition correspond to the edges of $G$ and the other side correspond to the vertices of $G$. Then $G$ has a clique of size $\omega$ if and only if the constructed bipartite graph has a ...


9

The Lovász $\vartheta$ function is an efficiently computable function with the property $$ \alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G), $$ where $\alpha$ is independence number and $\bar{\chi}$ is clique cover number. If the bound $\frac{\bar{\chi}(G)}{\alpha(G)} \leq n^{1-\varepsilon}$ were true for some constant $\varepsilon > 0$, then we would have ...


7

Correction: I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods. In fact, "Exact Cover" is contained in W[1]. It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & Grohe), and therefore lies in W[1]: ...


7

A decision variant, without the minimality condition, asking whether there is a set $B$ of size $n$ is called the set basis problem [SP7] in Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. The NP-completeness of it was proved by Stockmeyer.


6

This problem is way harder than set cover. Here is why... Intuitively, you can encode independent set as a problem of this type. Indeed, you are given an instance of independent set - a graph $G$ with $n$ vertices, and a number $k$, and the question is whether the graph $G$ has an independent set of size $k$. We assume that $k$ is large (say, polynomial in ...


6

If the required number of times we need to cover an element is 2, we have the following densest k-subgraph problem: (Imagine the edges are elements and nodes are sets.) Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum density. Khot proved that no PTAS exists under plausible complexity assumptions; there is an $O(n^{1/...


5

Yes, this has been studied. It was called the multiple intents re-ranking problem by Azar, Gamzu, and Yin who gave a $\log n$ approximation using a cleverly modified greedy algorithm (the point is being greedy with respect to a clever metric). Bansal, Gupta, and Krishnaswamy had the good sense to rename the problem to generalized min-sum set cover and gave a ...


5

If I'm not missing something, you can use a reduction from SINGLE OVERLAP RESTRICTED EXACT COVER BY 3 SETS (SINGLE OVERLAP RX3C) which I proved to be NPC in this cstheory question. EXACT COVER BY THREE SETS (X3C): Instance: Set $X=\{x_1,x_2,...,x_{3q}\}$ and a collection $C=\{C_1,...,C_m\}$ of 3-element subsets of $X$. Question: Does C contain an exact ...


5

Yes, this variant, and in fact a further generalization has been considered in the literature. See the paper below for the problem they call capacitated facility location. J. Bar-Ilan, G. Kortsarz and D. Peleg, Generalized submodular cover problems and applications, Theoretical Computer Science, 250:179-200, 2001.


5

We address this question in a new preprint: http://arxiv.org/abs/1512.00481 Hitting Set in hypergraphs of low VC-dimension (Karl Bringmann, László Kozma, Shay Moran, N.S. Narayanaswamy). It turns out that Hitting Set is W[1]-hard already when the VC-dimension is equal to 2.


5

This seems to have little to do with Banach-Tarski. In your setting, f is simply not an isometry due to floating-point errors, and in particular there must be a single piece $i$ such that $\mathrm{Vol}(f(P_i))>\mathrm{Vol}(P_i)$, so no need to cut into several pieces. Banach-Tarski works because the notion of volume is not well-defined on the pieces. ...


4

The approximation guarantee will be significantly worse. Assume you want to cover the set $U=\{1,\ldots,2n\}$. For every $i=1,\ldots,n$ define a set with n+1 elements by $S_i=\{i,n+1,\ldots,2n\}$. Assume we want to cover U with the sets $C=\{S_1,\ldots,S_n,U\}$, where $c(U)=2, c(S_i)=1$. We would now start with $C$ ans see that the effectivity of the sets $...


4

(Comment $\rightarrow$ Answer) Consider the following algorithms for a hypergraph $(U,\mathcal S)$, with $n=|U|$: For a set $X\subseteq \mathcal S$ of sets and a set $A \in X$, define $d_X(A)$ as the number of elements in $A$ that are double covered by $X$, i.e. $|A \cap \left(\bigcup(X \setminus \{A\})\right|$. Additionally, let $c(X)$ denote the number ...


4

This is an instance of the standard network flow problem called "Project Selection", and hence can be solved efficiently (even in practice). See (what's currently) Section 24.6 of Jeff Erickson's lecture notes for a nice explanation. It's covered in most introductions to network flow in good undergraduate algorithms courses, so if you don't like Jeff E's ...


4

This answers question (2): The greedy heuristic for Set Cover / Maximum Coverage always picks the set which contains the maximal number of uncovered elements. Assuming your modification for the heuristic is picking the set which greedily increases the solution profit, you might end up in a lousy approximation ratio. Consider the following example: $$A = \{...


4

Here I show that the problem is NP-complete. We convert a CNF to an instance of your problem as follows. Suppose that the variables of the CNF are $n$ $x_i$'s and the clauses are $m$ $C_j$'s, where $n<m$. Let $U=\cup_i (A_i\cup B_i\cup Z_i)$ where all sets in the union are completely disjoint. In fact, $A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\}$ and $...


3

Let me restate the first problem: Problem: Given a set of intervals $\mathcal{S} = \{ I_1, I_2,\ldots,I_n\}$, minimize $|\mathcal{C}|$, where $ \mathcal{C} =\{ I_{j_1}, I_{j_2},\ldots,I_{j_k}\} \subseteq\mathcal{S} $ and $ \bigcup_{l=1}^{n}I_l = \bigcup_{m=1}^{k}I_{j_m} $ Define: Graph $G(V,E)$, $V = \{v_1, v_2, \ldots, v_n ,s ,t \}$ where, Vertex $v_j \...


3

Perhaps this is a possible weird reduction from 3SAT. The idea is to use the set $S$ with restricted degree to simulate a true/false assignment to the variables using their odd/even distance from the clauses that contain them. Given a 3CNF formula with $n$ variables; let $c$ be the maximum among the number of occurrences of the variables in the clauses, and ...


2

Overview This problem is NP-hard; more precisely, the associated decision problem (in which we ask whether a target number of tridents $k$ can cover all of the given $x_i$s) is NP-hard. We will refer to this decision problem as the Numerical Trident Cover Problem. To prove that the Numerical Trident Cover Problem is NP-hard, we introduce the following ...


2

Lemma. The problem is NP-hard. Proof sketch. We disregard the constraints $|F_i| \ll n = |U|$ in the posted problem, because, for any instance $(F,U,k)$ of the problem, the instance $(F'=F^n,U'=U^n,k)$ obtained by taking the union of $n$ independent copies of $(F,U,k)$ (where the $i$th copy of $F$ uses the $i$th copy of $U$ as its base set) is equivalent, ...


2

Here is a paper that deals with this problem: John M. Ennis, Charles M. Fayle, and Daniel M. Ennis: Assignment-minimum clique coverings. Journal of Experimental Algorithmics 17(1), 2012. It also gives some heuristics and experimental results. They don't give worst-case approximation ratios; minimizing the number of cliques instead of the sum of their sizes ...


2

Sorry for answering my own question, but I found the answer quite clearly. To question 1: It turns out that this problem has been studied by Pauli Miettinen not too long ago. The intuitive name given to it is "The Positive-Negative Partial Set Cover problem". To question 2: Although the adapted trivial heuristic (each time picking the set which greedily ...


2

RestrictedExactCover is at least as hard as ExactCover, as ExactCover is a special case of RestrictedExactCover (the special case where $U=U'$). Also, clearly RestrictedExactCover is in NP. It follows that it is NP-complete.


2

The second definition uses the hitting set formulation, which is equivalent to the set cover problem. To see that, you may reverse the roles of sets and elements. You can find more information on the wikipedia page.


2

This is an upper bound on $N$ for the second formulation: Assume that I pick $N$ uniformly random sets. The probability of a pair of elements not to be covered by a specific set is $$1-\left(\frac{a}{L}\right)^2$$ Therefore the chance that it is not covered by any set is: $$\left(1-\left(\frac{a}{L}\right)^2\right)^N$$ Using the union bound, the chance ...


2

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time you cover an element, update the cost of all sets that cover it. Then there are n total updates, so the total time for the algorithm using a priority queue in ...


1

Having discussed with other users, I believe the following answers the question. To begin with let us recap the greedy algorithm for the set cover problem, in which we wish to cover all of $E$ as cheaply as possible. At each step, the algorithm adds the set $S_i$ for which $\frac{w_i}{|\hat{S}_i|}$ is lowest, where $\hat{S}_i$ is the subset of $S_i$ which ...


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