Hui Lu

One Rounding Fits All: Memory-Efficient Approximation Algorithms for Partition-Constrained Influence Maximization

RBwA, a memory-efficient and sample-efficient progressive sampling algorithm for IM-PC and a memory-efficient rounding scheme called BwARound for coverage maximization subroutines, which only requires storing one fractional vector and takes maximal feasible steps rather than tiny ε-increments, are proposed.