Problema APSP via Dimensão-VC e Médias de Rademacher
Resumo
Considere o problema de computar o caminho mínimo entre cada par de vértices (APSP) de um grafo, desde que o caminho tenha alta centralidade, sendo que a métrica de centralidade em questão reflete a "importância'' do caminho no grafo. Propomos um algoritmo para este problema que usa uma estratégia de amostragem baseada em Dimensão-VC e médias de Rademacher. No caso de grafos esparsos de diâmetro logarítmico, que comumente modelam situações reais, o tamanho da amostra é exponencialmente menor do que aquelas obtidas por técnicas clássicas (e.g.: Hoeffding e limitante da união).
Palavras-chave:
Problema APSP, Algoritmo de Aproximação, Dimensão-VC, Médias de Rademacher
Referências
de Lima, A. M., da Silva, M. V. G., e Vignatti, A. L. (2020). Estimating the percolation centrality of large networks through pseudo-dimension theory. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD).
Easley, D. e Kleinberg, J. (2010).Networks, crowds, and markets. Cambridge University Press.
Har-Peled, S. e Sharir, M. (2011). Relative (p,ε)-approximations in geometry. Discrete & Computational Geometry, 45(3):462–496.
Oneto, L., Ghio, A., Anguita, D., e Ridella, S. (2013). An improved analysis of the rademacher data-dependent bound using its self bounding property. Neural Networks, 44:107 – 111.
Pettie, S. e Ramachandran, V. (2002). Computing shortest paths with comparisons and additions. In Proc. of ACM-SIAM Symp. on Discrete Algorithms, pages 267–276.
Riondato, M. e Upfal, E. (2018). Abra: Approximating betweenness centrality in static and dynamic graphs with rademacher averages. ACM Transactions on Knowledge Discovery from Data, 12(5):61:1–61:38.
Williams, R. (2014). Faster all-pairs shortest paths via circuit complexity. In Proc. of the Forty-sixth Annual ACM Symp. on Theory of Computing, STOC ’14, pages 664–673.
Easley, D. e Kleinberg, J. (2010).Networks, crowds, and markets. Cambridge University Press.
Har-Peled, S. e Sharir, M. (2011). Relative (p,ε)-approximations in geometry. Discrete & Computational Geometry, 45(3):462–496.
Oneto, L., Ghio, A., Anguita, D., e Ridella, S. (2013). An improved analysis of the rademacher data-dependent bound using its self bounding property. Neural Networks, 44:107 – 111.
Pettie, S. e Ramachandran, V. (2002). Computing shortest paths with comparisons and additions. In Proc. of ACM-SIAM Symp. on Discrete Algorithms, pages 267–276.
Riondato, M. e Upfal, E. (2018). Abra: Approximating betweenness centrality in static and dynamic graphs with rademacher averages. ACM Transactions on Knowledge Discovery from Data, 12(5):61:1–61:38.
Williams, R. (2014). Faster all-pairs shortest paths via circuit complexity. In Proc. of the Forty-sixth Annual ACM Symp. on Theory of Computing, STOC ’14, pages 664–673.
Publicado
18/07/2021
Como Citar
LIMA, Alane M. de; VIGNATTI, André L.; SILVA, Murilo V. G. da.
Problema APSP via Dimensão-VC e Médias de Rademacher. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 6. , 2021, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 13-16.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2021.16369.
