Durezza della copertura esatta di cardinalità minima approssimativa

Question

Il problema MCEC (Cardinality Exact Cover (MCEC) è proprio come la copertura del set, ma i set di output devono essere disgiunti.

Formalmente, data una raccolta di sottoinsiemi $ s $ di un set limitato $ u $, il problema chiede una subcollezione $ s '$ di $ s $ di cardinalità minima in modo tale che l'unione di $ s' $ sia $ u $ e $ S_1 cap s_2 = vuoto $ per ogni distinto $ s_1, s_2 in s '$.

Potremmo presumere che per ogni $ u in u $ 'esiste un set $ s_u = {u } $ in $ s $. Ciò garantisce che esista una copertura esatta di cardinalità al massimo $ | u | $.

Vorrei sapere se MCEC è difficile da approssimare come la copertura impostata, IE non può essere approssimato all'interno di un fattore $ log | u | $. Posso dimostrare che MCEC non ha un'approssimazione costante del fattore, riducendo da $ k $ -set-cover per qualsiasi $ k $ costante aggiungendo ogni sottoinsieme di un set presente nell'input di copertura set. Ma avere la stessa inapprossimabilità della copertura impostata sarebbe più forte.