Dynamic Algorithms for k Center Problems

PhD Thesis Proposal 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 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[71]. 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 proposal, we study some dynamic versions for the k center problems 
and variants. We propose some dynamic algorithms, and give theoretical 
analysis of these algorithms.


Date:			Monday, 8 May 2023

Time:                  	10:00am - 12:00noon

Zoom Meeting:
https://hkust.zoom.us/j/94453044219?pwd=M0oyMzZwMkZhQmYySlNUWHdwYmlhUT09

Committee Members:	Prof. Mordecai Golin (Supervisor)
 			Prof. Ke Yi (Chairperson)
 			Prof. Siu-Wing Cheng
 			Dr. Amir Goharshady


**** ALL are Welcome ****