Clustering has many applications in multiple areas, e.g., operations research and machine learning. The k-center problem is one of the most basic clustering problems....[ Read more ]

Clustering has many applications in multiple areas, e.g., operations research and machine learning. The k-center problem is one of the most basic clustering problems.

Over the last few decades, there has been much work on the k-center problem and its variants. The k center problem aims to place at most k centers that service all clients, trying to minimize the service cost which is the maximum over all clients of the minimum work required for the client to be serviced by one of the centers (this is usually just the min distance from a client to one of the centers.)

The standard k-center problem is known to be NP-hard to approximate with a factor smaller than 2 for arbitrary metric spaces[72]. 2-approximation algorithms for this problem are well-known. There are variations of the k center problem that arise in practice, for example, the Euclidean k center problem, the k center problem with outliers, and the fair k center problem.

Let P be a set of points in some metric space. In many practical applications, the data set P is not static but changes dynamically over time, e.g, a new point may be inserted to or deleted from P at each step. The solution of the problem then needs to be recomputed at selected query times. If only insertions are permitted, the problem is incremental; if both insertions and deletions are permitted, the problem is fully dynamic.

In this thesis, we study some dynamic versions of k center problems and some of its variants. We propose dynamic algorithms, and give theoretical analysis of these algorithms. In particular, this thesis begins by developing new dynamic algorithms for the k-center and Euclidean k-center problems that work by plugging a new algorithm for dynamic approximate furthest neighbor into known static algorithms.

After that we use coreset techniques to develop dynamic algorithms for solving approximate versions of variations of the k-center problem including fair k-centers, k-center with outliers and the sum of radii problem.

We conclude by providing efficient algorithms for exactly solving the dynamic k-center on trees problem.