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.