Preguntas etiquetadas con ds.algorithms

16
?

Mientras leía el blog de Dick Lipton, me topé con el siguiente hecho cerca del final de su publicación de Bourne Factor : Si, por cada nnn , existe una relación de la forma (2n)!=∑k=0m−1akbckk(2n)!=∑k=0m−1akbkck (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} donde m=poly(n)m=poly(n)m = poly(n) , y...

16
¿Por qué las relaciones de aproximación diferencial no están bien estudiadas en comparación con las estándar a pesar de sus beneficios declarados?

Existe una teoría de aproximación estándar donde la relación de aproximación es supAOPTsupAOPT\sup\frac{A}{OPT} (para problemas conobjetivosMINMINMIN),AAA- el valor devuelto por algún algoritmoAAAyOPTOPTOPT- un valor óptimo. Y otra teoría, la deaproximación diferencialdonde la relación de...