A Survey of Facility Location Problems on Trees

PhD Qualifying Examination


Title: "A Survey of Facility Location Problems on Trees"

by

Mr. Jinxiang GAN


Abstract:

Over the last few decades, there has been a lot of work on facility 
location problems, in particular, the k-center and k-median problem and 
variations. These problems place facilities that service clients, trying 
to minimize the service cost under some metric. While most 
facility-location problems are NP-hard on general networks, they are 
usually polynomial-time solvable on restricted graphs such as paths and 
trees. Even restricted to such special cases there has still been a lot of 
work on devising the most efficient algorithms for those graphs. In this 
survey, we review the literature of solving the network location problems 
on paths and trees, summarize some of the important techniques developed 
and propose possible directions for future research.


Date:			Thursday, 2 September 2021

Time:                  	2:00pm - 4:00pm

Zoom meeting:
https://hkust.zoom.com.cn/j/93379002126?pwd=VjRWNGQyQ1FuWVByTjJ5TDc1QkY4dz09

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


**** ALL are Welcome ****