We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency $L$ of a schedule is the maximum latency of any site, where the latency of a site $s$ is the supremum of the lengths of the time intervals between consecutive visits to $s$. When $k=1$ the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into $\ell$ groups, for some~$\ell \leq k$, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a $1+\varepsilon$ factor loss in the approximation factor and an $O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for any $\varepsilon >0$. Our second main result shows that an optimal cyclic solution is a $2(1-1/k)$-approximation of the overall optimal solution. Note that for $k=2$ this implies that an optimal cyclic solution is optimal overall. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a $(2(1-1/k)+\varepsilon)$-approximation of the optimal unrestricted solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting.

Technology innovation has provided the opportunity to study the characteristics of natural human mobility. In this paper, we look at how to identify interesting clusters (by different individuals or other naturally defined groups) in a family of trajectory traces. We focus on coarse-grained, sparsely sampled trajectories inferred from sporadic occurrences in an unsupervised setting. This is a challenging setting due to difficulties in selecting features and similarity measures, and due to lack of prior knowledge of data distribution. We propose a non-parametric clustering algorithm, which makes little assumptions on prior knowledge of both data distribution and cluster properties. Our algorithm, Conformal DBSCAN, combines density-based DBSCAN clustering with the statistical conformal prediction framework. We first identify groups of highly similar trajectories as the initial seeds of clusters, similar to DBSCAN. Then we include additional trajectories that belong to this cluster, with a guaranteed statistical confidence level, derived by an improved conformal prediction framework. This allows the clustering algorithm to automatically adapt to different data distributions. Our algorithms are shown to significantly outperform alternative clustering algorithms on several artificial and real-world datasets.

In this paper, we propose co-evolution models for both dynamics of opinions (people's view on a particular topic) and dynamics of social appraisals (the approval or disapproval towards each other). Opinion dynamics and dynamics of signed networks, respectively, have been extensively studied. We propose a co-evolution model, where each vertex i in the network has a current opinion vector vi and each edge (i, j) has a weight wij that models the relationship between i, j. The system evolves as opinions and edge weights are updated over time by the following rules: Opinion dynamics: The opinion of agent i is updated as a linear combination of its current opinion and the weighted sum of neighbors' opinions with coefficients in matrix W = [wij]. Appraisal dynamics: The appraisal wij is updated as a linear combination of its current value and the agreement of the opinions of agents i and j. The agreement of opinion vi and vj is taken as the dot product vi · vj. We are interested in characterizing the long-time behavior of the dynamic model–i.e., whether edge weights evolve to have stable signs (positive or negative) and structural balance (the multiplication of weights on any triangle is non-negative). Our main theoretical result solves the above dynamic system with time-evolving opinions V(t) = [v1(t), …, vn(t)] and social tie weights W(t) = [wij(t)]n×n. For a generic initial opinion vector V(0) and weight matrix W(0), one of the two phenomena must occur at the limit. The first one is that both sign stability and structural balance (for any triangle with individual i, j, k, wijwjkwki ≥ 0) occur. In the special case that V(0) is an eigenvector of W(0), we are able to obtain the explicit solution to the co-evolution equation and give exact estimates on the blowup time and rate convergence. The second one is that all the opinions converge to 0, i.e., limt→∞ |V(t)| = 0. We also performed extensive simulations to examine how different initial conditions affect the network evolution. Of particular interest is that our dynamic model can be used to faithfully detect community structures. On real-world graphs, with a small number of seeds initially assigned ground truth opinions, the dynamic model successfully discovers the final community structure. The model sheds lights on why community structure emerges and becomes a widely observed, sustainable property in complex networks.

Advances in wireless communication technology have allowed for the collection of large-scale human motion trajectories by recording the appearance of mobile devices within the neighborhood of wireless base stations. Such city-scale datasets pose new challenges on efficient data collection, analysis and similarity based queries. In this paper, we propose new partial similarity measures, categorized as time-sensitive, order-sensitive and order-insensitive ones, and show with real data that these partial similarity measures are more robust than classical measures and more suitable for generating meaningful query results in near-neighbor type of data mining applications. Further, the power of the partial similarity persists even with significant down-sampling. We presented rigorous analysis of the performance of partial similarity measures with subsampling. Our evaluation using real data shows high recall and precision (≥ 90%) with samples only in the order of 1% of the original data size.

Beacon-based time-of-flight indoor localization systems have shown great promise for applications ranging from indoor navigation to asset tracking. In large-scale deployments, a major practical challenge is determining the placement of a minimal number of beacons that ensures full coverage -- each point in the domain has line-of-sight paths to enough beacons to uniquely localize itself. Three beacons with line-of-sight paths are always enough, but two beacons within line of sight may also work, given a favorable geometry. In this paper, we propose two beacon placement algorithms that leverage the floor plan geometry with provable theoretical guarantees. First, we present a greedy algorithm using properties of sub-modular functions to place O(OPT · ln m) beacons, where m is the number of discrete location points in the region that need to be localized, and OPT is the size of the optimal solution. Second, we present a random sampling algorithm that places O (OPT · log(OPT)) beacons while localizing all targets. We evaluate our algorithms on both real-world and randomly generated floor plans. Our algorithms place on an average 6 ~ 23% and 12% fewer beacons in real-world topologies and randomly generated floor plans respectively, as compared to prior work. We also present a study where we ask users to attempt to place nodes manually and discover that even humans that are well versed on the coverage problem find it hard to balance the trade-off between the number of beacons and area localized.

Wireless relay network has been widely used in many applications to improve the wireless service. In this paper, we aim to maximize users' satisfaction by deploying limited number of relays in a target region to form a wireless relay network, and define the Deployment of Cooperative Relay (DoCR) problem, which is proved to be NP-complete. We first propose two approximation algorithms, an O(logn) algorithm that utilizes the algorithms for budget weighted Steiner tree problem with novel position weighting assignment, and an O(√k) algorithm that iteratively scans potential positions and determines relay placement plan with the help of submodular function theory, partition technique, and greedy strategy. We name them Relay Effective Deployment Algoirthm (REDA) and Submodular Iterative Deployment Algorithm (SIDA), respectively. We further propose Gradient-Descent Based Algorithm (GDBA), a heuristic method, to solve the DoCR problem releasing potential location constraints. Our extensive experiments indicate that the algorithms we propose can significantly improve the total satisfaction of the network. Furthermore, we establish a testbed using USRP to showcase our designs in real scenarios. To the best of our knowledge, we are the first to propose approximation algorithms for relay placement problem to maximize user satisfaction, which has both theoretical and practical significance in the related area.

In this paper, we aim to maximize users' satisfaction by deploying limited number of relays in a target region to form a wireless relay network, and define the Deployment of Cooperative Relay (DoCR) problem, which is proved to be NP-complete. We first propose an O(δ log n) approximation algorithm that utilizes the algorithms for budget weighted Steiner tree problem with novel position weighting assignment. We further propose a heuristic method to solve the DoCR problem releasing potential location constraint. Our extensive experiments indicate that the algorithms we propose can significantly improve the total satisfaction of the network. Furthermore, we establish a testbed using USRP to showcase our designs in real scenarios. To the best of our knowledge, we are the first to propose approximation algorithm for relay placement problem to maximize user satisfaction, which has both theoretical and practical significance in the related area.