Seja uma família de subconjuntos de elementos- de um universo finito de objetos. Uma família de subconjuntos de elementos de , com , é um conjunto de batidas de - se para cada existir pelo menos um conjunto tal que .
Dada uma colecção como descrito acima, a - bater-conjunto problema é encontrar um menor -hitting-conjunto de por .
Quando , temos o problema do conjunto de resultados padrão e há muitos resultados anteriores. Conheço análises parametrizadas para o caso com e (ver Brankovic e Fernau , por exemplo).
Alguém conhece algum resultado sobre a complexidade ou a dureza da aproximação do problema do conjunto de batidas com:
- e ?
- e ?
- e arbitrária?
fonte