Questions tagged [exact-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
0answers
146 views

Approximating set cover when it is known that an exact set cover exists

Suppose $U = \{1, 2, \cdots, n\}$ is a universe and $\mathcal S = \{S_1, S_2, \cdots, S_m\}$ is a collection of sets such that each set contains exactly $c$ elements, where $c$ is a constant. In this ...
2
votes
0answers
59 views

An Exact Cover Variant encoded in a 4-Terminal Network

During research, I hit the following problem Exact Cover Variant (ECV) Input: Three set systems $S_1, S_2, S_3$ over a universe $U$, each closed with respect to $\cap$ and $\cup$. ...
7
votes
1answer
454 views

Parameterized complexity of Exact Cover

Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^* \...
0
votes
1answer
1k views

exact cover set problem

i am searching an heuristic algorithm for a weighted exact cover problem shown here: http://en.wikipedia.org/wiki/Exact_cover On my research i only found algorithm which calculates all solutions ...
1
vote
2answers
214 views

Covering by disjoint sets

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. I'm interested in the approximability of two problems, or in ...