BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1408
DTSTAMP:20240514T040141Z
SUMMARY:Knapsack: Connectedness\, Path\, and Shortest-Path
DESCRIPTION:Speaker: Palash Dey (Indian Institute of Technology\, Kharagpur
 )\n\nAbstract: \nWe study the Knapsack problem with graph-theoretic constr
 aints. That is\, there exists a graph structure on the input set of items 
 of Knapsack and the solution also needs to satisfy certain graph theoretic
  properties on top of the Knapsack constraints. In particular\, we study C
 onnected Knapsack where the solution must be a connected subset of items w
 hich has maximum value and satisfies the size constraint of the knapsack. 
 We show that this problem is strongly NP-complete even for graphs of maxim
 um degree four and NP-complete even for star graphs. On the other hand\, w
 e develop an algorithm running in time O(2^{tw log tw} · poly (n) min{s^2
 \, d^2}) where tw\, s\, d\, n are respectively treewidth of the graph\, th
 e size of the knapsack\, the target value of the knapsack\, and the number
  of items. We also exhibit a (1 − epsilon) factor approximation algorith
 m running in time O(2^{tw log tw} · poly (n\, 1/epsilon)) for every epsil
 on > 0. We show similar results for Path Knapsack and Shortest Path Knapsa
 ck\, where the solution must also induce a path and shortest path\, respec
 tively. Our results suggest that Connected Knapsack is computationally the
  hardest\, followed by Path Knapsack and then Shortest Path Knapsack.\nSho
 rt Bio:\nProf. Palash Dey is an Assistant Professor in the Department of C
 omputer Science and Engineering at the Indian Institute of Technology Khar
 agpur. Before joining IIT Kharagpur\, he spent around a year as a visiting
  post-doctoral fellow at the School of Technology and Computer Science (ST
 CS) at Tata Institute of Fundamental Research (TIFR) Mumbai. Before that\,
  he finished his PhD and Master of Engineering from the Department of Comp
 uter Science and Automation in 2017 and 2013\, respectively. He received t
 he INSPIRE Faculty Award in 2018 and the ACM India Best Dissertation Award
  in 2017. He has been a fellow of the West Bengal Academy of Science and T
 echnology\, Government of West Bengal\, India\, since 2022 and an INAE You
 ng Associate since 2023. He is an ACM India Eminent Speaker for 2024-26. H
 is research focuses on Algorithmic Game Theory and Parameterized Algorithm
 s.\n
URL:https://www.tcs.tifr.res.in/web/events/1408
DTSTART;TZID=Asia/Kolkata:20240604T160000
DTEND;TZID=Asia/Kolkata:20240604T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR