Algorithms on Clustering, Orienteering, and Conflict-Free Coloring

Chen, Ke

Permalink

https://hdl.handle.net/2142/11396 Copy

Description

Title

Algorithms on Clustering, Orienteering, and Conflict-Free Coloring

Author(s)

Chen, Ke

Issue Date

2007-10

Keyword(s)

algorithms

Abstract

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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11396

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections