Los algoritmos de flujo requieren aleatorización en su mayor parte para hacer algo no trivial, y debido a la restricción de espacio pequeño, necesitan PRG que usen poco espacio. Sé de dos métodos que se han citado para su uso en algoritmos de flujo hasta ahora:
- -wise PRGs independientes como la familia independiente 4-sabia utilizado por Alon / Matias / Szegedy para el original F 2 problema de estimación, y generalizaciones para los métodos basados en 2-estabilidad para (por ejemplo) ℓ 2 bosquejar
- El PRG de Nisan que funciona en general para cualquier tipo de problema de espacio pequeño.
Estoy particularmente interesado en los métodos que se pueden implementar. A primera vista, los dos enfoques anteriores parecen relativamente fáciles de implementar, pero tengo curiosidad por saber si hay otros por ahí.
ds.algorithms
derandomization
streaming
pseudorandom-generators
Suresh Venkat
fuente
fuente
En muchos algoritmos geométricos, el muestreo aleatorio puede ser reemplazado por redes ε y aproximaciones ε (de algún espacio de rango apropiado con dimensión de VC finita) y estos pueden ser mantenidos eficientemente por un algoritmo de transmisión - vea mi artículo "Muestreo determinista y conteo de rango en geometría Flujos de datos "con Bagchi, Chaudhari y Goodrich de SoCG 2004 y ACM Trans. Alg. 2007 .
fuente
J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, Z. Svitkina, "Sobre la distribución de computaciones de transmisión simétrica", SODA 2008.
fuente