# Tag Info

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

8

Here's one randomized $O(\log n)$-approximation algorithm (not well known I'm afraid), for unit-cost set cover. input: collection of sets over $n$ elements, upper bound $U$ on opt output: w/probability $\ge 1/2$, a set cover of size $O(U \ln n)$. Let $K=\lceil \ln(2n)U/0.99\rceil$. Let $T=\ln(100)$. Create $K$ tokens, each with an associated unit-rate ...

7

I don't see how you can say that SCP or any other problem has "worst-case asymptotic complexity", but surely an algorithm solving it can have. However, the problem is NP-complete, and the optimization version is NP-hard. For an exact algorithm, this is clearly a "theoretical limit". For an exact algorithm, see for example E. Balas and M. C. Carrera, A ...

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

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. It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & Grohe), and therefore lies in W: ...

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 Given that a cover exists, greedy will return a cover of expected size$O(p^{-1}\log n)$. As long as$k$is not too large, with high probability every cover has size$\Omega(p^{-1}\log n)$This implies that (for$k$not too large) greedy gives an$O(1)$-approximation with probability$1-\delta$, for any constant$\delta>0$. Here is the upper bound, ... 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. 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$nx_i$'s and the clauses are$mC_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$...

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 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 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-hard already when the VC-dimension is equal to 2. 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 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 ... 3 The problem you're asking to solve is a variant of the k-median problem on a metric space. You haven't mentioned anything about the various sizes involved, but as a formal matter, there are only n choices for the magic number k (the number of centers), and so after "guessing" the right value of k, you can run any of the standard approximation ... 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 ... 3 sometimes with various CS optimization problems, the best available or most evolved implementations can be found in EE applications. in this case, consider Espresso, a logic minimizer. its open source and mainly written in C. it has a built in [exact] and also heuristic set cover as a subroutine after generating prime implicants for SAT. the exact covering ... 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 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_is) 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 ith copy of F uses the ith copy of U as its base set) is equivalent, ... 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

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

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