7 votes

Minimal generator for a set of sets

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-...
user6192's user avatar
5 votes
Accepted

Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover

It's also NP-hard, because Set Cover on sets of constant size is NP-hard, and given an instance of Set Cover with constant-size sets, you can add all the (polynomially many) subsets of the given sets, ...
Neal Young's user avatar
  • 10.8k
5 votes

Can the Banach-Tarski paradox be "realized" by floating-point round-off?

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}...
Denis's user avatar
  • 8,853
4 votes
Accepted

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

(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 ...
Yonatan N's user avatar
  • 1,642
4 votes
Accepted

Complexity of Finding Optimal Synergistic Set Packings

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 ...
Andrew Morgan's user avatar
3 votes

Covering a binary relation as a union of rectangles

...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions. Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-...
Chris Culter's user avatar
3 votes

Set cover with small subsets

Set cover for $d=2$ is the edge cover problem, which is a poly-time problem [1]. For $d=3$, it is indeed NP-complete. This can be shown using the same reduction from 3SAT to 3-dimensional matching ...
user3209423940248's user avatar
3 votes
Accepted

Balanced set coloring

I think this question is closely related to the term discrepancy. Here is the defintion. Given a universe $U$ a collection of sets $\mathcal{A}=\{S_i\}$ and a function $\varphi:U\to\{-1,1\}$. For $S\...
TheHolyJoker's user avatar
3 votes

Known Variant of Set Cover?

We can abstract this problem as submodular minimization (minimize additional covers) under submodular cover (set cover) constraint. I'll point you towards two papers in this area. Iwata and Nagano, ...
darwinflinches's user avatar
2 votes

Restricted Universe Exact Cover

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 ...
D.W.'s user avatar
  • 12.1k
2 votes
Accepted

Definition of k-set cover

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 ...
Yixin Cao's user avatar
  • 2,559
2 votes

Is the following problem NP hard?

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,...
Neal Young's user avatar
  • 10.8k
2 votes
Accepted

Set Cover with Multiple covers

This answer expands on Chandra's comment. We'll prove two lemmas that show that $q=O(\log m)$ is a necessary condition for Properties (1) and (2) to hold, and that this bound is tight in the sense ...
Neal Young's user avatar
  • 10.8k
2 votes

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

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 ...
David Eppstein's user avatar
2 votes
Accepted

Set cover with rewards

Seems to be in P, as it seems to be equivalent to max-wt independent set (equivalently min-wt vertex cover) in a bipartite graph, which is in P. Specifically, construct the bipartite graph $G=(U, \...
Neal Young's user avatar
  • 10.8k
1 vote
Accepted

How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

Lemma 1. The problem is NP-hard. Proof. By reduction from Clique. Given an instance $(G=(V,E), k)$ of Clique (with $k<|V|$), the reduction produces the instance of OP's problem defined as follows. ...
Neal Young's user avatar
  • 10.8k
1 vote
Accepted

Set cover where consecutive sets differ by at most one item

Take an arbitrary instance $S_1,\ldots,S_n$ of SET COVER. Between $S_1$ and $S_2$, insert a chain of new subsets $$ S_1-x,~ S_1-\{x,y\},~ \ldots,~ \{z\},~ \emptyset,~ \{c\},~ \ldots,~ S_2-\{a,b\},~ ...
Gamow's user avatar
  • 5,772
1 vote

CNF encoding of set cover - NExpTime-completness

As I suspected in my question, they are useful results in the literature that can be exploited to characterize the complexity of the problem. There is a reduction from the dominant set problem for ...
Jean-Francois Raskin's user avatar
1 vote

Partial cover approximation

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 ...
John Harrison's user avatar

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