School of Technology and Computer Science Seminars

Online Algorithms for Node-weighted Network Design

by Dr. Debmalya Panigrahi (Duke University, USA)

Monday, February 3, 2014 from to (Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
Description
In recent years, an online adaptation of the classical primal-dual paradigm has been successfully used to obtain new online algorithms for node-weighted network design problems, and simplify existing ones for their edge-weighted counterparts. In this talk, I will give an outline of this emerging toolbox using three fundamental problems in this category for illustration: the Steiner tree problem (Naor-P.-Singh, 2011), the Steiner forest problem (Hajiaghayi-Liaghat- P., 2013), and their respective prize-collecting variants (Hajiaghayi-Liaghat-P., 2014).