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