Problema APSP via Dimensão-VC e Médias de Rademacher

Abstract

We consider the version of the All-pairs Shortest Paths (APSP) problem, where we are only required to compute paths with high centrality, such that the centrality metric reflects the “importance” of a path in the graph. We propose an algorithm for this problem that uses a sampling approach based on VC-Dimension and Rademacher averages. In the case of sparse graphs with logarithmic diameter, which is a common model for several real-world scenarios, the sample size is exponentially smaller than those obtained by classical techniques (e.g. Hoeffding and union bound).