Abstract
Let $G=(V,E,w)$ be a finite, connected graph with weighted edges. We areinterested in the problem of finding a subset $W \subset V$ of vertices andweights $a_w$ such that $$ \frac{1}{|V|}\sum_{v \in V}^{}{f(v)} \sim \sum_{w\in W}{a_w f(w)}$$ for functions $f:V \rightarrow \mathbb{R}$ that are `smooth'with respect to the geometry of the graph. The main application are problemswhere $f$ is known to somehow depend on the underlying graph but is expensiveto evaluate on even a single vertex. We prove an inequality showing that theintegration problem can be rewritten as a geometric problem (`the optimalpacking of heat balls'). We discuss how one would construct approximatesolutions of the heat ball packing problem; numerical examples demonstrate theefficiency of the method.