2019/01/23 by Hung T. Nguyen, Nguyen, Hung, Phuc Thai +7
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Optimization and Search Problems #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1901.07928
openalex publication_date 2019/01/23 · openalex created_date 2019/02/21 · openalex updated_date 2026/07/28
Given a weighted hypergraph H(V, E ⊆ 2V, w), the approximate k-cover problem seeks for a size-k subset of V that has the maximum weighted coverage by sampling only a few hyperedges in E. The problem has emerged from several network analysis applications including viral marketing, centrality maximization, and landmark selection. Despite many efforts, even the best approaches require O(k n log n) space complexities, thus, cannot scale to, nowadays, humongous networks without sacrificing formal guarantees. In this paper, we propose BCA, a family of algorithms for approximate k-cover that can find (1-(1)/(e) -ε)-approximation solutions within an \emphO(ε-2n log n) space. That is a factor k reduction on space comparing to the state-of-the-art approaches with the same guarantee. We further make BCA more efficient and robust on real-world instances by introducing a novel adaptive sampling scheme, termed DTA.