¿Cuáles son los buenos algoritmos de aproximación para el problema de suma de subconjuntos hasta ahora?

Respuestas:

11

Kellerer y col. (1997) da con precisión un esquema de aproximación de tiempo O ( min { n / ϵ , n + 1 / ϵ 2 log ( 1 / ϵ ) } ) y O ( n + 1 / ϵ ) .ϵO(min{n/ϵ,n+1/ϵ2log(1/ϵ)})O(n+1/ϵ)

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

No estoy seguro de si hay resultados más nuevos. Como se señaló, debido a que la suma de subconjuntos es un caso especial del problema de la mochila, uno probablemente encontrará aún más resultados al buscar eso.

O(n3/ϵ)

Juho
fuente
n
@JuanBermejoVega ¡Correcto!
Juho