Algorithms on Clustering, Orienteering, and Conflict-Free Coloring

We present algorithms for three geometric problems -- clustering, orienteering, and conflict-free coloring. In the first part, we obtain small coresets for k-median and k-means clustering in general metric spaces and in Euclidean spaces. In R^d, these coresets have size that depend polynomially on d. This leads to more efficient approximation algorithms for k-median and k-means clustering. We use those coresets to maintain a (1+\eps)-approximate k-median and k-means clustering of a stream of points in R^d, using O(dk^2 \eps^{-2} log^8 n) space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension. We next study the k-median clustering with outliers problem. Here, given a finite point set in a metric space and parameters k and m, we want to remove m points (called outliers), such that the cost of the optimal k-median clustering of the remaining points is minimized. We present the first polynomial time constant factor approximation algorithm for this problem. In the second part, we consider the rooted orienteering problem: Given a set P of n points in the plane, a starting point, and a length constraint B, one needs to find a path starting from r that visits as many points of P as possible and of length not exceeding B. We present the first polynomial time approximation scheme (PTAS) for this problem. The scheme also works in higher (fixed) dimensions. In the last part, we present randomized algorithms for online conflict-free coloring of points in the plane, with respect to intervals, halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all these cases, the coloring algorithms use O(log n) colors, with high probability. We also present the first efficient deterministic algorithm for the CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(log^12 n) colors