Published on Mon Mar 19 2018

### Numerical Integration on Graphs: where to sample and how to weigh

,

Let be a finite, connected graph with weighted edges. We prove an inequality showing that the integration problem can be rewritten as a geometric problem. We discuss how one would construct approximate solutions of the heat ball packing problem.

0
0
0
###### Abstract

Let be a finite, connected graph with weighted edges. We are interested in the problem of finding a subset of vertices and weights such that $$\frac{1}{|V|}\sum_{v \in V}^{}{f(v)} \sim \sum_{w \in W}{a_w f(w)}$$ for functions that are smooth' with respect to the geometry of the graph. The main application are problems where is known to somehow depend on the underlying graph but is expensive to evaluate on even a single vertex. We prove an inequality showing that the integration problem can be rewritten as a geometric problem (the optimal packing of heat balls'). We discuss how one would construct approximate solutions of the heat ball packing problem; numerical examples demonstrate the efficiency of the method.