  In location-based social networks (LBSNs), such as Gowalla and Waze, users
sense urban point-of-interest (PoI) information (e.g., restaurants' queue
length and real-time traffic conditions) in the vicinity and share such
information with friends in online social networks. Given each user's social
connections and the severe lags in disseminating fresh PoI to all users, major
LBSNs aim to enhance users' social PoI sharing by selecting a subset $k$ out of
all $m$ users as hotspots and broadcasting their PoI information to the entire
user community. This motivates us to study a new combinatorial optimization
problem by integrating two urban sensing and online social networks. We prove
that this problem is NP-hard and also renders existing approximation solutions
not viable. Through analyzing the interplay effects between the sensing and
social networks, we successfully transform the involved PoI-sharing process
across two networks to matrix computations for deriving a closed-form objective
and present a polynomial-time algorithm to ensure
($1-\frac{m-2}{m}(\frac{k-1}{k})^k$) approximation of the optimum. Furthermore,
we allow each selected user to move around and sense more PoI information to
share. To this end, we propose an augmentation-adaptive algorithm, which
benefits from a resource-augmented technique and achieves bounded
approximation, ranging from $\frac{1}{k}(1-\frac{1}{e})$ to $1-\frac{1}{e}>
0.632$ by adjusting our augmentation factors. %Particularly when all sensing
nodes are associated with users, we devise, by leveraging our
augmentation-adaptive algorithm as a subroutine, an algorithm that eliminates
the need for augmentation while still ensuring a satisfactory approximation
$1-\frac{m-2}{m}(\frac{k-1}{k})^k$. Finally, our theoretical results are
corroborated by our simulation findings using both synthetic and real-world
datasets.

Social and Information Networks;Discrete Mathematics;Data Structures and Algorithms