Dynamic Algorithms for k-Center Problems

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Dynamic Algorithms for k-Center Problems"

By

Mr. Jinxiang GAN


Abstract:

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 minimum 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, while 2-approximation
algorithms for this problem are well-known. There are also other 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
this 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 should then be efficiently recomputed, rather than computed from
scratch, at selected query times.

In this thesis, we study dynamic versions of the k-center problem and many of
its variants. We propose new algorithms for solving them, and give theoretical
analyses of these algorithms.


Date:                   Tuesday, 12 December 2023

Time:                   10:00am - 12:00noon

Venue:                  Room 5566
                        Lifts 27/28

Chairman:               Prof. Patricia LIEM (MAE)

Committee Members:      Prof. Mordecai GOLIN (Supervisor)
                        Prof. Amir GOHARSHADY
                        Prof. Siu Wing CHENG
                        Prof. Ajay JONEJA (IEDA)
                        Prof. Robert BENKOCZI (University of Lethbridge)


**** ALL are Welcome ****