Por "bom", quero dizer, ou o algoritmo fornece um limite relativamente apertado ou possui um tempo de execução relativamente rápido. Qualquer referência é bem vinda.
8
Por "bom", quero dizer, ou o algoritmo fornece um limite relativamente apertado ou possui um tempo de execução relativamente rápido. Qualquer referência é bem vinda.
Respostas:
Melhorando ainda mais, Kellerer et al. (2003) fornece um FPTAS com tempo e espaço. Além disso, respondendo à sua pergunta sobre "tempo de execução relativamente rápido", eles observaram que (com base nos resultados computacionais) que o esquema resolve com eficiência instâncias com até itens com um erro relativo garantido menor que .O(min{n⋅1/ϵ,n+1/ϵ2log(1/ϵ)}) O(n+1/ϵ) 5000 1/1000
Não tenho certeza se existem resultados mais recentes. Como observado, como a soma do subconjunto é um caso especial do problema da mochila, provavelmente você encontrará ainda mais resultados ao procurar por isso.
ATUALIZAÇÃO: Você também pode dar uma olhada no The Design of Approximation Algorithms, Williamson e Shmoys, 2011 , consulte o capítulo que começa na página 65 sobre o problema da mochila. Eles fornecem um FPTAS (na página 68) para o problema da Mochila que é executado no tempo . Pode ser que os algoritmos projetados especificamente para o problema da soma de subconjuntos sejam mais rápidos que os mais gerais para a mochila.O(n3/ϵ)
fonte