Dureté de l'approximation de la couverture exacte de la cardinalité

Question

Le problème minimum de la couverture exacte (MCEC) est comme la couverture de set, mais les ensembles de sortie doivent être disjoints.

Formellement, étant donné une collection de sous-ensembles $ s $ d'un ensemble fini $ u $, le problème demande une sous-collection $ s '$ de $ s $ de cardinalité minimale telle que le syndicat de $ s' $ est $ u $, et $ S_1 cap s_2 = videset $ pour chaque $ distinct $ s_1, s_2 in s '$.

On peut supposer que pour chaque $ u dans u $ ', il y a un ensemble $ s_u = {u } $ dans $ s $. Cela garantit qu'il existe une couverture exacte de la cardinalité au plus $ | u | $.

Je voudrais savoir si MCEC est aussi difficile à approximer que la couverture définie, c'est-à-dire que le facteur $ log | u | $ ne peut pas être approximé dans un $ log | u | $. Je peux montrer que MCEC n'a pas d'approximation de facteur constant, en réduisant de $ k $ -set-couvercle pour toute $ k $ constante en ajoutant chaque sous-ensemble d'un ensemble présent dans l'entrée de couverture de jeu. Mais avoir la même inapproximabilité que la couverture de set serait plus forte.