We describe an efficient streaming-model construction of epsilon-nets and epsilon-approximations, and use it to find deterministic streaming-model approximation algorithms for iceberg range queries and for various robust statistics problems.
Studies the resilience of distributed computation networks against adversarial and random fault models; shows that, in both models, certain networks can withstand constant fault probabilities and still contain a large subnetwork with similar expansion to the original.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.