- In this paper, we consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set P of n (weighted) demand points, and the location of each demand point P_i∈P is uncertain but is known to appear in one of m_i points on T each associated with a probability. Given a covering range \lambda, the problem is to find a minimum number of points (called centers) on T to build facilities for serving (or covering) these demand points in the sense that for each uncertain point P_i∈P, the expected distance from P_i to at least one center is no more than $\lambda$. The problem has not been studied before. We present an O(|T|+M\log^2 M) time algorithm for the problem, where |T| is the number of vertices of T and M is the total number of locations of all uncertain points of P, i.e., M=\sum_P_i∈Pm_i. In addition, by using this algorithm, we solve a k-center problem on T for the uncertain points of P.
- Apr 26 2017 cs.DS arXiv:1704.07791v1Small depth networks arise in a variety of network related applications, often in the form of maximum flow and maximum weighted matching. Recent works have generalized such methods to include costs arising from concave functions. In this paper we give an algorithm that takes a depth $D$ network and strictly increasing concave weight functions of flows on the edges and computes a $(1 - \epsilon)$-approximation to the maximum weight flow in time $mD \epsilon^{-1}$ times an overhead that is logarithmic in the various numerical parameters related to the magnitudes of gradients and capacities. Our approach is based on extending the scaling algorithm for approximate maximum weighted matchings by [Duan-Pettie JACM`14] to the setting of small depth networks, and then generalizing it to concave functions. In this more restricted setting of linear weights in the range $[w_{\min}, w_{\max}]$, it produces a $(1 - \epsilon)$-approximation in time $O(mD \epsilon^{-1} \log( w_{\max} /w_{\min}))$. The algorithm combines a variety of tools and provides a unified approach towards several problems involving small depth networks.
- Principal component analysis (PCA) is a fundamental dimension reduction tool in statistics and machine learning. For large and high-dimensional data, computing the PCA (i.e., the singular vectors corresponding to a number of dominant singular values of the data matrix) becomes a challenging task. In this work, a single-pass randomized algorithm is proposed to compute PCA with only one pass over the data. It is suitable for processing extremely large and high-dimensional data stored in slow memory (hard disk) or the data generated in a streaming fashion. Experiments with synthetic and real data validate the algorithm's accuracy, which has orders of magnitude smaller error than an existing single-pass algorithm. For a set of high-dimensional data stored as a 150 GB file, the proposed algorithm is able to compute the first 50 principal components in just 24 minutes on a typical 24-core computer, with less than 1 GB memory cost.
- Apr 26 2017 cs.DS arXiv:1704.07710v1
- Apr 26 2017 cs.DS arXiv:1704.07708v1
- Apr 26 2017 cs.DS arXiv:1704.07625v1
- Apr 26 2017 cs.DS arXiv:1704.07546v1
- Apr 26 2017 cs.DS arXiv:1704.07406v1