We present new approximation algorithms for the k-median and k-means clustering problems. To this end, we obtain small coresets for k-median and k-means clustering in general metric spaces and in Euclidean spaces. In $\mathbb{R}^d$, these coresets are of size with polynomial dependency on the dimension d. This leads to $(1+\varepsilon)$-approximation algorithms to the optimal k-median and k-means clustering in $\mathbb{R}^d$, with running time $O(ndk+2^{(k/\varepsilon)^{O(1)}}d^2\log^{k+2}n)$, where n is the number of points. This improves over previous results. We use those coresets to maintain a $(1+\varepsilon)$-approximate k-median and k-means clustering of a stream of points in $\mathbb{R}^d$, using $O(d^2k^2\varepsilon^{-2}\log^8n)$ space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension.

We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use O (log n ) colors, with high probability. We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O (log 3 n ) colors. This is the first efficient (i.e, using polylog( n ) colors) deterministic online CF coloring algorithm for this problem.

We consider the rooted orienteering problem: Given a set P of n points in the plane, a starting point $r \in P$, 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 a $(1-\varepsilon)$-approximation algorithm for this problem that runs in $n^{O(1/\varepsilon)}$ time; the computed path visits at least $ (1-\varepsilon)k_{\mathrm{opt}}$ points of P, where $k_{\mathrm{opt}}$ is the number of points visited by an optimal solution. This is the first polynomial time approximation scheme for this problem. The algorithm also works in higher dimensions.

We consider an online version of the conflict‐free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict‐free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.

We study the problem of conflict-free (CF) coloring of a set of points in the plane, in an online fashion, with respect to halfplanes, nearly-equal axis-parallel rectangles, and congruent disks. As a warm-up exercise, the online CF coloring of points on the line with respect to intervals is also considered. We present randomized algorithms in the oblivious adversary model, where the adversary does not see the colors used. For the problems considered, the algorithms always produce valid CF colorings, and use O(logn) colors with high probability (these bounds are optimal in the worst case). Our randomized online algorithms are considerably simpler than previous algorithms for this problem and use fewer colors.We also present a deterministic algorithm for the CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(polylog(n)) colors. This is the first efficient deterministic online CF coloring algorithm for this problem.

We consider the orienteering problem: Given a set P of n points in the plane, a starting point r ∈ P, and a length constraint B, one needs to find a tour starting at r that visits as many points of P as possible and of length not exceeding B. We present a (1−ε)-approximation algorithm for this problem that runs in nO(1/ε) time, and visits at least (1−ε)kopt points of P, where kopt is the number of points visited by the optimal solution. This is the first polynomial time approximation scheme (PTAS) for this problem. The algorithm also works in higher dimensions.