The k-server problem is one of the most fundamental problems in the area of online algorithms. In this problem, an online algorithm needs to maintain a set of k servers in a metric space. When a request arrives at a certain location, one of the k servers needs to move to this requested location. The goal is to minimize the total movement cost of all the servers. Over the past three decades, significant progress has been made on this problem, yet many intriguing questions remain open. Notably, progress on the k-server problem has resulted in the development of new techniques that have advanced the broader field of online algorithms. This talk will survey recent techniques and breakthroughs developed for the k-server problem.
Short Bio:
Amit Kumar is a faculty member in the dept. of Computer Science and Engineering at IIT Delhi. He obtained a B.Tech. degree from IIT Kanpur in 1997 and Ph.D. from Cornell University in 2002. He works in the area of combinatorial optimization, with emphasis on problems arising in scheduling, graph theory and clustering. He
received IBM Faculty Award in 2005, INAE (Indian National Academy of Engineering) Young Engineer Award in 2006 and INSA (Indian National Science Academy) Medal for Young Scientists in 2011. He was a Max Planck-India partner group research fellow during 2005-09. He received the prestigious Shanti Swarup Bhatnagar Award for Mathematical Sciences in 2018, and was elected Fellow of Indian Academy of Sciences in 2019, and Fellow of Indian National Academy of Engineering in 2022.
