Quais são os bons algoritmos de aproximação para o problema de soma de subconjuntos até agora?

Respostas:

11

ϵO(min{n/ϵ,n+1/ϵ2log(1/ϵ)})O(n+1/ϵ)

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{n1/ϵ,n+1/ϵ2log(1/ϵ)})O(n+1/ϵ)50001/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/ϵ)

Juho
fonte
n é o número de números inteiros a somar, certo?
Juan Bermejo Vega
@JuanBermejoVega Correct!
Juho