Por "bueno", quiero decir que el algoritmo proporciona un límite relativamente estrecho o tiene un tiempo de ejecución relativamente rápido. Cualquier referencia es bienvenida.
8
Por "bueno", quiero decir que el algoritmo proporciona un límite relativamente estrecho o tiene un tiempo de ejecución relativamente rápido. Cualquier referencia es bienvenida.
Respuestas:
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/ϵ)
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.
fuente