Tata Institute of Fundamental Research
Online Algorithms for Node-weighted Network Design
Seminar
Speaker:
Debmalya Panigrahi (Duke University
Department of Computer Science
Campus Box 90129
308, Research Drive (LSRC Building)
Durham, NC 27708
United States of America)
Organiser:
Kavitha Telikepalli
Date:
Monday, 3 Feb 2014, 15:45 to 17:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: 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).
| Speaker: | Debmalya Panigrahi (Duke University Department of Computer Science Campus Box 90129 308, Research Drive (LSRC Building) Durham, NC 27708 United States of America) |
| Organiser: | Kavitha Telikepalli |
| Date: | Monday, 3 Feb 2014, 15:45 to 17:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: 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).