Files in this item



application/pdfAlgorithms on C ... Conflict-Free Coloring.pdf (835kB)
(no description provided)PDF


Title:Algorithms on Clustering, Orienteering, and Conflict-Free Coloring
Author(s):Chen, Ke
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.
Issue Date:2007-10
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2007-2901
Rights 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).
Date Available in IDEALS:2009-04-22

This item appears in the following Collection(s)

Item Statistics