We look into the problem of estimating the average of quantities relating to combinatorial and geometrical objects. In all the cases we study it is possible to get the exact average of these quantities by using the trivial algorithm that calculates the average by obtaining all the quantities. Using the underlying structure of these problems, we are able to obtain faster algorithms that approximate the average. Specifically, we consider randomized algorithms that are given an approximation parameter epsilon, and return a (1+epsilon)-approximation of the average quantity. Our work focuses on the problem of calculating the average degree of a hypergraph, and the problem of calculating the average distance between every pair of points in a set of points in a d-dimensional Euclidean space.
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, February 2007.
Available: the thesis (in PS format).
|
|
|
| |||
| Kfir as Hermes | delivers a message | gets punished |
Back to Oded Goldreich's homepage.