Empacotamento de conjuntos: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m WP:BOT: Substituindo sintaxe matemática obsoleta de acordo com mw:Extension:Math/Roadmap |
|||
Linha 45:
A versão ponderada também pode ser aproximada assim.<ref>{{Citar conferência|last=Halldórsson|first=Magnus M.|year=1999|title=Approximations of weighted independent set and hereditary subset problems|conference=5th Annual International Conference on Computing and Combinatorics|series=Lecture Notes in Computer Science|volume=1627|publisher=Springer-Verlag|pages=261–270}}</ref>
No entanto, o problema tem uma variante que é mais tratável: se nós não assumimos nenhuma subconjunto excede ''k''≥3 elementos, a resposta pode ser aproximada dentro de um fator de ''k''/2 + ε para qualquer ε > 0; em particular, o problema com 3 conjuntos de elementos pode ser estimado em cerca de 50\%. Em outra variante mais tratável, se nenhum elemento ocorre em mais de ''k'' de subconjuntos, a resposta pode ser aproximada dentro de um fator de ''k''. Isso também é verdadeiro para o versão ponderada.
== Problemas equivalentes ==
| |||